The classic example, as Tom mentioned, is where to meet in Paris if
no prior agreement was made. As potential tourists, we tend to find
the answer of the Eiffel tower satisfactory.
However, if we were artists, and in Europe to visit art museums,
we might choose the Louvre.
Given just a slight variation on the character of the participants,
a different answer seems quite reasonable. A larger variation, to
a methane-breathing BEM, makes almost anything seem reasonable, as
long as it is important to the BEM. He may find the discharge pipe
from Paris' nuclear power plant particularly facinating.
However, the one constant that sticks out in all of these is uniqueness.
Try the previous examples with multiplicity: if Eiffel had built two
similar towers, which one do you choose? If the Uffizi were also in
Paris? If Paris has two nuclear power plants? None of them work anymore.
The BEM's view of the world may be terribly different from ours, but
I'll wager that he can distiquish 'one' from 'many'. (He has to
be able to, if he can handle the concept of a Schelling point.)
Thus he can reach the same conclusion about uniqueness that we can.
With this in mind, Tom's suggestion of the galactic center may not
be facetious. The center may be impractical if there is a big black
hole there, but it is unique.
While it is not clear to me if the entire discussion is about physical
locations or points on the radio frequency spectrum, the classic
'waterhole' does not appear unique. It is one of many frequencies that
has good penetration characteristics. It may seem natural to us water
based critters, but a hydroxyl group may be arcane chemistry to the BEM.
There is not only the 'what frequency' question, but 'where do we
aim the antenna.'
The fastest solution may be to solve the FTL problem ( or at least
fast sublight ), send a transmitter to the galactic center or other
unique galactic feature, and broadcast from there.