I sometimes find that a stroke, glow or drop shadow is useful, but not at full strength. I like to start with a 1 pixel stroke in a color complementary to the text. I reduce the opacity of the stroke to 0 (I know you can do that in Photoshop, not sure about Gimp), and then increase it until I feel like the text's legibility is optimized. If the label is very large, or I get all the way to 100% opacity without seeing improvement, then I'll start adjusting other parameters. The key is to use just enough, and no more.

It is also important to have sufficient color contrast between the labels and the underlying imagery. I think the black on deep blue is getting a bit lost because the values are so similar. Try something like a very pale yellow on the ocean to start with. That color might also work for labels over the green areas, but it definitely will not work over the desert, where you'll want a darker label.

Well-made, non-decorative fonts are important. There are plenty of good fonts with high legibility that can evoke high fantasy, or science fiction, or pirates, or whatever. A decorative font is great for a map's title or a really huge label, but the smaller the text is, the less a decorative font is desirable.

Regarding serif vs sans serif: It doesn't really matter so much for labeling a map, but serif fonts are usually more readable, so they're preferred for body copy. Readability is a measure of how much fatigue a typeface causes in large blocks. Legibility is a measure of how quickly a headline can be comprehended. Serif fonts tend to have a stylistic association with a time period that is post-industrial revolution and pre-information age.