Have a look at this older thread. The typefaces mentioned there do not have a hand-lettered look, but are 19th/early 20th century grotesques, or inspired by such.

Maybe something like this?
http://new.myfonts.com/fonts/larstornqvist/simpliciter-sans/

Ogentroost Hand might be suitable.

Type won't capture the charming irregular quality of words like LIBERTY, or GREENSBURG's bend.
Your best bet is to draw the letters as paths in Illustrator, and then stroke those paths.
That will also provide consistency of line in different sizes (e.g. FIFTH and VIRGIN).
It will be meticulous and time-consuming work, but will produce far better results than auto-tracing letter outlines.
The effect will still be a somewhat unnatural, compared to the original engraved script, but that should be mitigated by the medium of granite etching.

I was worried somebody would tell me that I had to do this all by hand! I definitely see how tracing the letters will result in a final design that feels more like the original. And the more I researched fonts, the more I realized that an exact match does not exist.

I had thought about using a font like Gotham Rounded or something like that and scaling / hand placing each letter individually, on top of the map graphic, to preserve scale and spacing. Still thinking it all over. And will share the final results...

I appreciate everybody's input!

Nice suggestions here. Nick, is right of course. But if you want to start with type, do think irregular. Gotham Rounded is too consistent. Even tho it's more early 1900s and German, DIN 17 (derived from template-assisted hand-lettering) might be more appropriate with some adjustments.

Thanks for all your advice!

I took Nick's advice and did not try alter the original map with any overset text. Instead I worked with the map graphic in illustrator to try to make the text as rounded and legible as possible. Anything else would have not preserved the hand crafted character of the original graphic. The trickiest part was working with Live Trace. I had to make sure that the graphic got simplified but not overly abstracted.

The map will be approximately 16' x 16'. We were pretty excited to see the mock up sample.

We were pretty excited to see the mock up sample.

Me too! Thanks for following up.