Here we go...
I made 3 text samples: Cities (Steden), Geography (don't need to translate that one, do I?) and Rivers/water (ditto). Countries use the same type/style as cities, but larger, depending on available space. Cities are all the same size, except capitals, which are a point larger and bold. Rivers all use the same type/style, water features are labelled as space permits. Fonts used are Frutiger for man-made features (cities and countries), Minion Pro for anything geographic. Some exceptions though...
(same view, at different zooms)
Shown here are the original texts, 3 options for texts on water and 2 options for text on land. Font sizes shown here are the smallest used on the maps. I figure if I can make it work for those, it'll be good for everything.
Water, option 1: 10Y 10K for city and geography names, 50C for water names
Water, option 2: 40C 20M for everything
Water, option 3: 20C 10M for everything
Those last 2 are Dennis' suggestions.
Land, option 1: 100K with a 0.7pt 10K outline for cities and geography, 100C 60M with a 0.7pt 10K outline for water.
Land, option 2: Same as 1, but water text a bit darker (100C 75M) and the outline set to 75% transparency. Makes it less prominent, but it still does the job.
I've fiddled a lot with the land texts, these were the only ones that work well across the globe, with the possible exception of high mountain ranges, which show up as light grey mottled with darker greys. In those few cases, I'll probabely enlarge the type and/or the outline. Also, there's places where the standard black text (no outline) contrasts well with the terrain (deserts mainly), there I will simply keep it that way.