Look at the various versions of Bell Centennial - know as the "phone book font" but as promoted by info graphic expert Edward Tuft as a really good font for small info.

Cisalpin: The ideal typeface for cartography

The Swiss designer/typographer Felix Arnold designed Cisalpin during the late 1990s, after he had challenged himself to create a contemporary typeface that could be used for cartographic uses. Arnold came to the subject of cartographic typefaces after analyzing many maps and atlases, and discovering that there was no standard typeface for these types of documents.

London A to Z uses Gill Sans, if I remember right.

I remember a publication by the National Geographic Society about their maps, in which they wrote of the virtues of using hand lettering, or typefaces that resembled hand lettering, for maps.

Cisalpin, a sans serif, would seem to win the prize for clarity in messy situations and at small sizes.
There are serif cartographic typefaces that have variations for specific information, e.g. rivers as opposed to cities. For example Roemisch http://www.myfonts.com/fonts/linotype/roemisch/ and Kursivschrift http://www.myfonts.com/fonts/linotype/kursivschrift/
Don

I am a cartographer with more than 22 years of experience. I had few bad experiences with fancy fonts and my advise is to use for road labels extremely readable condensed fonts like Arial Narrow.
If you are ready to buy one, here you are a commercial font designed for cartographers: http://www.linotype.com/2276/cisalpin.html
Andras

Would you consider commissioning something new? A map typeface to be used online at small sizes have very specific requirements. You need large apertures, big x-height, simplified features, clear contrast between various pieces of information and possibly condensed styles, maybe a set of symbols, and all of it has to be hinted to render clearly across all modern browsers.

If the font needs to "follow curves well", doesn't this mean it will be used in generating map images, rather than used in a web font?

Of course, there are some presentation techniques used on the Web that do allow text to be laid out in curves - PostScript, and hence one's map could be an Adobe .PDF file.

Ah, I see I'm out of date. Text in Google Maps sometimes follows curves.