Just to reiterate, the easiest way (in my experience) to get underwater is assassins (indies only, of course). Constr 2 gets you amulets of water breathing, and UW commanders are generally weaker than land commanders (just watch out for the occassional powerful W mage).
5 gems (3 w/ hammer) and 100 g (for assassin) is a nice investment for a water province.
Good option for Jomon to get into those new UW units.
Oceania and Atlantis tend to have really good recruitable priests, even natural H3. They'd need to be in small lake surrounded by your dominion, preferably with blood sacrificers, to make it work.