An idea sprung to my mind, gills aren't really used for much of anything, so.. why not make randomly generated ocean map with sunken boats that you can enter to nab randomly generated stuff within, or find bloated corpses with money on them, etc. Also would have oceanic monsters to increase the danger of being in the ocean map.
I imagine it'd be fun for treasure hunters.