I'd like to expand on Freehand's first line a little bit. There are two related qualities a font has: readability and legibility. Readability is how easy the font is to read over long stretches. It's a quality that is important to body copy and not so much to maps. The other term, legibility, is how easy it is to comprehend a single word in the font; it's important to headlines and map labels.

Generally speaking, readability is improved by serif fonts, but since we're not concerned with body copy, the choice between serif, sans serif and decorative is largely a matter of style and personal taste. Legibility, on the other hand, is of primary importance, particularly on a map with a large number of labels. Most decorative fonts, such as you'd find at an online repository like Dafont.com, are poorly designed and can be quite illegible. In addition, they usually feel a bit heavy-handed when used as map labels. They can be okay for very large labels, particularly over a flat area, like the ocean, or for the map's title bar, if it has one. For smaller, more numerous labels, I would be inclined to choose a simple, professionally set font. There are good fonts that fit most settings. For instance, I like Belwe for many fantasy maps—it has a nice Celtic flavor. You can sometimes use an amateur's font if you're willing to spend the time doing some manual kerning or other touching up. (Kerning refers to the space between the letters. You can adjust it in Adobe applications by placing your font in the gap you want to change, holding down alt, and using the left- and right-arrows to move the right-hand side of the gap.)

While an outline or a glow can help with legibility, do not go overboard. I like to start with a 1-pixel outline, then reduce the opacity until the labels lose legibility, then bring it back up slightly: just enough to improve it without looking like an effect. Likewise with glows—just enough to wash out the details beneath the label so that they no longer interfere with the text. Another approach is to make a copy of your labels, turn it into a mask, expand it slightly, then use that to mask out the lines layers, in effect cutting holes in the map where your text can live comfortably.

I'm going to politely disagree with Freehand concerning the number of typefaces on a document. I wouldn't use more than three fonts in a single map. One for large labels, one for small ones, and maybe a third for cartouches. You can get some additional variety by adjusting size and color, and by using the italics variant. I prefer to let the symbols indicate what a particular feature is rather than using a different font.