[thejeff]

You can also recruit amphibious independents. Icthyids, mostly.
Or an amphibious pretender. A Wyrm can take most underwater indies from turn one. Once you've got a foothold, you can recruit underwater troops.

It's hard to fight actual water nations that way, but it's a start.