I am really interested in ways a map can communicate to players to help them make choices. Zak had the great idea of using the fonts of place names to convey some sense of the place. I think in addition to that we might make more use of symbols on the map. I know that sounds ridiculously obvious, but maybe I need to think about it a little more.
First, these do exist and have for a while, the symbols for ancient battlefields on the map of Basic D&D's The Known World come to mind (Though I wonder why. Are there undead armies lurking there at night?). Fantasy maps often show caves or mines on them. All these can give players a sense of what exploration choices they have. But I'm thinking a little more feature rich, something like a tourist road map. I have seen these all my life but the google oracle is being dense today. This tourist map of Turkey is sort of what I'm thinking of:
My world map probably would be a little more sparse, a little less cartoony. But the idea is there. Like most fantasy maps you have your ancient ruins located. But also, if there are nomadic tribes to the east, it's probably common knowledge. Or if a region is known to have precious gems or valuable furs they would have symbols on the maps. Waterfalls, rapids, huge canyons, hot springs, bandits, large carnivores, there are lots of possibilities.
The idea isn't that the map is accurate. It's an abstraction of general knowledge of the area. So, no one in the home town or local keep has necessarily been to the marshes down south in generations, but they know tribespeople keep bringing amber out of that region to trade. And those traders might mention circular ruins.
Another influence in my mind on this topic are the resource icons for the video game Civilization, at least those in the first two versions. Internet bonus points if you can point us to some nice examples or resources for useful thematic map icons.