Thank you all for the replies (and the warm welcome!)

I guess what (intuitively) bothers me concerning the color transition is the stylistic mix. I decided not to shoot for an "old parchment" look, but rather move towards an artistic/light/fairy-kind of direction which suits my campaign style better.

Having a colour outline to mountain zones with drawn mountains in the zone is used pretty frequently in drawing fantasy maps (one of those tropes), so it doesn't jar with me. It could be that maps which use that convention rarely (I've never seen one from memory) have feathering between one land type and another, so there is a consistency or internal rule that land types on the map is defined with solid colours.
Exactly. At one point, I re-worked all transitions and used a hard-edged brush instead of a soft-edged one to give it a more painterly look. Good decision: What had been quite indistinct and washed-out now looked better and also made more sense from a semantic point-of-view. I guess this is what you mean by "solid colors". I tried to walk a fine line between "color banding" and blending colors seamlessly.

You could create some city icons with that same approach, or you can stick with the geometric icons you have.
I thought about this as well... geometric icons work surprisingly well, but I guess even those I need to paint by hand to stay consistent.

The coastline glow, though, fades very gently from light to dark blue. I think it would look nicer if you painted the shallows on, so the water and land matched.
Good idea. Gotta try that. Not sure if that's leading inevitably to a buccaneer-style map though (ahoy mateys! where's my parrot?) ;-)