It's hard to do, but often it's best to wait for at least the alpha version of the game before getting real worried about final polished art. When making a game, and you do things out of order, much time can be wasted, therefore decreasing the likelihood of actually completing it.
ENVIRONMENT IDEAS:
- Warm tinted cavernous and/or open water areas molded by underwater volcanic eruptions minor and major (blobby curvilinear rock formations, glowing veins of magma between formations, strange flora/fauna adapted to the heat, fire/heat element oriented enemies)
- Abyss full of phosphorescent creatures (shifting light sources, remember Aquaria's abyss stage. . .)
- World War II wreckage from a huge battle (remains of subs, planes littering ocean seabed, some large enough to enter)
- Atlantis (Merfolk civilization, think Little Mermaid but less gay, could be ruins or a still-functioning city)
- Bermuda Triangle (ruins of ships/planes, and . . . you'll have to think of an explanation for all the unexplained disappearances blamed on the Bermuda Triangle and reveal it in the level)
- Swallowed by a whale (whale inards, walking on tongue, swimming in stomache)