... then it certainly would look less like an overlay of a sat map. If you look closely at Iceland, it seems to work because the border lines are closer to the underlying base color than they are to the overlay colors of the continents, it adds depth.
Since you don't want to use overlay colors, then there is no way of using that trick. Buy you could "sink" the boundary lines into the sand with appropriate shadow. Or you can use the Iceland "trick", and just use overlays that are each a slightly a different shad of red (since that's where you seem to like to go), and then small gaps for the boundaries.... I know very little how this works, so if I talking about stuff that's impossible, just feel free to ignore.
