Have you found the excellent guide Ravells posted on positioning labels? Lots of goodness there.

The saturated colors are a style statement, a bold one. Since there's plenty you want labelled on this, perhaps you should experiment with a less saturated or lighter palette, to let the labels show up better? If your focus is the land, using less saturation on the sea makes it recede from notice a bit.

If the lighter water just means shallows, it looks mighty uniform. Take a look at Earth's continental shelves - they vary from zero width to hundreds of miles across. If it's just a device to set off the otherwise similar-value land and sea, consider a coastline stroke instead, and/or lightening either land or sea.

Is this for paper publication or an eBook? If paper, you may want to create a simpler B&W version for print, relegating the colored one to supplemental material in your online presence. Bonus material to give readers a reason to come to a website, shall we say. If for an eBook you can get away with a lot that can't be economically printed... but it's still support material for the story. I presume you want readers to be able to see where events take place, and to be able to locate places that characters themselves never visit, bu only speak of? If so, the legibility may matter more than the style. If your purpose is to set forth your world's aesthetic, to imply a period - then the look could matter as much as the content. Almost :-).