What are thoughts on best modulation to use for underwater acoustic communications at low frequencies?
That is a nasty signal environment.  I would do a little DSP judo and make the multi-path work for you by using a rake receiver, which should make the multi-path signals increase your SNR rather than diminish it.

Rake receivers have only been used (as far as I know, anyway) in CDMA systems, but that is not because they can only be used in CDMA systems.  The issue is the symbol period.  The following quote is from a paper on rake receivers:


  RAKE receiver attempts to
  collect the time-shifted versions of the original signal by
  providing a separate correlation receiver for each of the
  multipath signals. This can be done due to multipath
  components are practically uncorrelated from another when
  their relative propagation delay exceeds a chip period.


Thus, the reason that they were used in CDMA systems and not, say, GSM, was because the chip speed was so much faster, and thus the multipath signals would not arrive in the same chip/symbol.  That was not true for GSM and other "narrowband" signals.  Even though your bit rate is very low, the multipath signals still seem to have delays greater than one symbol, so this constraint should not be a problem.

The other problem is detecting the multipath.  This could, I would think, be accomplished with known data sequences, such as a preamble, but I confess that I am not an expert on rake receivers.

If the rake receiver does not work out, you could still use a long equalizer to handle the multipath.

Regarding the other elements of the system, if there is no feedback I would do a QPSK signal with FEC (probably turbo codes).  If you do have feedback I would do the same but also dynamically change the modulation type from QPSK up to 16-QAM or something, depending on how well the signal is coming through.

EDIT: After thinking about it a bit I realized why rake receivers and CDMA systems go hand-in-hand.  The problem is that even if you detect a multi-path signal it doesn't do you a lot of good unless it has a positive SINR.  By definition at most one multi-path signal can have a positive SINR, because for all the other multi-path signals the strongest overwhelms them.

That is where despreading comes in.  Once the multi-path signal is despread it will have a positive SINR, assuming the spreading factor is large enough to overcome the initial negative SINR.  Given this I think the right solution is to relax the 500 Hz limit, use a fairly large spreading factor and a rake receiver to combine the various multi-path signals.