I also suggest the map have important points like towns labeled and to allow map modification in the form of user created labels, icons or colored pins. This map would definitely need a zoom function and the map's graphics must be clear and nice.
It would also be nice to be able to "quick travel" from town to town as you discover them. One way to do this is to have the player rent a coach for 100 gold per trip (or something like that) as the coach, horses, and protection are expensive. You could even have towns they refuse to go to if you like.
Later in their adventures, say a certain adventure level, the player could even get a quest for a traveling stone, a magical stone of teleportation that does the same job as the coach but takes something to use, say rubies for instance. The big difference is that this stone can be used anywhere outside, just select and choose from a list of already visited locations. You could even forgo the coach and use the stone from early on if ya like.

The main thing would to be at least getting a working ingame map, though. This game is sorely lacking without one, even though I still love it.

DarkSavant13