To meet the quality of the artwork, Ilanthar, I'd say none of those fonts work well. Although, the second one is better.

Have you ever tried IM Fell? GreatWhiteNorth directed me to it in a WIP I'm finishing and I fell in love with them. Either with this map or sometime down the road, you should try it.... here's a link: The Fell Types.

Also, I think using a midtone brown instead of black would do wonders for those labels.

Those are my two cents..