What are the constraints on the data used to generate/select the graphics for the map?
It seems the current logic selects the character/tile to use based on a precedence list, with the biome at the bottom and (probably) inhabited sites at the top, with volcanoes, summits, and rivers in between. If the current logic remains that constrains what can be done (you can't e.g. show elevation beyond the implicit one of mountains being high elevation by definition, and you can't show a river cutting through a dry broadleaf forest). I don't even know if the current logic allows for a better biome discrimination than the broad biome type ("jungle", mountain, hills, etc.) displayed currently, although the tropicality (i.e. tropical/temperate version) is actually shown today, as is the evilness level.
I assume you won't be able to dig down to the mid level tile level (those on the leftmost map) for the top level tile, as digging up that information takes far too much time (we're talking minutes for a maximum size world), but it ought to be possible to e.g. overlay a biome tile with a river overlay.
My preference would be to show as much information as possible, so each biome would have its own image, with an overlay for river (preferrably differing between brook/stream and the river sizes, and obviously variants for the various ways it can cross the tile, including merges) and other overlays for summits and volcanoes. Caves (when shown) ought to be possible to show as an overlay as well, while habitations would probably have to take over the tile completely (although necro towers might join caves as being possible to show on top of the biome). Showing elevation would be a nice addition as well.
Once it's known what can be shown (or probably can be shown, as I'd expect the display selection code to have to change to show more than what's shown now, and so wouldn't be nailed down completely before it's actually done), the next step would be to decide what you'd try to display and what would have to be sacrificed, which would be both a technical one (what can be done with the pixels available), and an art style one.
I wouldn't go for a "real" map style unless the mid level tile info was available, as you'd really need that level of biome boundary information to produce a good looking map, and at that point it wouldn't really be tile based (the character version would still have to be, though, but it also wouldn't look like a parchment map regardless). As indicated above, that isn't really feasible now, but might be something to strive for after the map rewrite (and, if so, would provide an input requirement/request for the rewrite).
gchristopher's point about the ability to actually locate desired sites is a good one, so a grid toggle would probably be helpful with a post map rewrite parchment style map.