Cave provinces!

[HoneyBadger]

For the deep sea, you could have the Diving Bell magic item (level 4 constr. allows you and 25 human-sized troops to venture into the deepest parts of the ocean, also allows waterbreathing) and the Nautilus artifact (level 8 constr. You and up to 300 troops can sail 20,000 leagues into the depths of the sea and return without harm-waterbreathing and 100% darkvision included). Amulet of the Fish should allow both air travel for waterbreathers and deep ocean travel for everyone, since the sphere of water it produces would have to be self-pressurizing to retain integrity. One or two other items already in the game might allow access too, but again, it's not the ability to "breathe water", it's the pressure you'd have to worry about, and it should be significantly more difficult to overcome lack of air, high pressure, and total darkness.