A few further questions:
How close are the labels going to be to one another? The more breathing room, the more flexibility you have.
How much will labels vary and on what basis? You don't want a stew of 20 different fonts, but if you have to use 20 distinct label types, you'll want to choose a family that shows enough difference between italic and Roman, and amongst different weights.
Do you need to print text using a printing technology (B&W laser or offset press) that uses dot screens? This requires a lot of planning ahead to make it work. See my paper in
Cartographic Perspectives, Number 47, Winter 2004 for more thoughts on the subject: the entire issue is
here as a PDF).
Don't give up on the "super basic" fonts like Arial, but consider the range of usable variants in Helvetica (Personally I usually use Helvetica Neue), Univers, and Frutiger. Lately I've been gravitating to Griffith Gothic also. And our "home base" at Hedberg Maps, Avenir, which I really think is hard to beat for small-size legibility.
And consider variants among serif fonts. Times is legible, especially for text, but look at options with higher lower-case heights. I like Sabon becuase its italic is very legible, and I've often gone to Minion because it complements "basic" serif fonts so well. Going fancier I've used Berkeley and Goudy Old Style just because they are such gorgeous fonts, and Kennerley because it evokes a certain kind of pre-World-War-II nostalgia for me.
Hope this helps.