From an out-of-water perspective, we normally fill land with more than one color, using separate colors to identify forest/plain/mountain. And then we simply use shades of blue to suggest not everything is equal under the sea surface.
Don't know how this would work, but at such a starting point of your project, why not trying the opposite thing: one color in different shades for land, a variety of colors for sea (sandy sea plains, deep sea, coralian areas, i don't know).