Oh my! There are literally THOUSANDS of fonts out there on sites like Dafont.com (which is the one I tend to trawl) and you can get really bogged down or even fall asleep choosing one, there are just so many.
Google 'free fonts' and you'll pretty quickly discover most of the main sites.
Font choice is such a very personal thing, a bit like your favourite colour or taste, that it would be impossible for me to guess what the ideal font would be for you. I would suggest that the best and only way is to go looking at what there is for yourself.
Guidelines - try not to fall in love with anything that is grossly ornate or distorted. Those kinds of fonts look great on a poster ad, but they're pretty much rubbish in a map because they are hard to read, and map labels are meant at the very least to be legible. The other one you already know - a graceful font might look very nice, but they tend to have lots of thin bits in the individual letters that disappear if they are used at a small scale.
Before you go racing off to google everything, though, just check out what you've already got available on your system by flipping open that font box in GIMP, as the last thing you want to do is bog down your PC with a thousand different new fonts, if you already have the one you like right there.
One rule: Never use Papyrus!!! Its got a really bad name around here because it was totally overused to death in the early days of fantasy cartography