I can see why you might not want to treat each area individually. Do you need the sea? Assuming not.
(edit: I hope the images you are working on are larger than the size the example seems to be.)
One way is using colour selections and selection-to-path
01. Reduce the number of colours. Several ways but I favour changing the image mode to indexed
Image -> Mode -> Indexed
screenshot:
https://i.imgur.com/6tzQsFM.jpg
02. I put the colormap map up for reference in the screenshot, but colour select each required colour (maybe sea is not required) and for each selection make a path.
Select -> To Path Good idea to keep the path visibility on for each path to see progress.
screenshot:
https://i.imgur.com/dEng69N.jpg
03. Now convert back to RGB
Image -> Mode -> RGB (and a good time to save your image as a Gimp .xcf file with those paths). You can keep the separate paths or combine into one - right click, merge visible paths.
screenshot:
https://i.imgur.com/1pjD8DB.jpg
04. Make a new layer for a border overlay. Stroke the path(s)
Edit -> Stroke Path
screenshot:
https://i.imgur.com/cbco6RX.jpg
05: Now Import the original back in
Open as Layers and put under the border overlay.
screenshot: