One idea I liked from WoW, was that you had to actually explore a place before you could see it on the map. When you first entered a zone for the first time, the map was completely blank. As you ventured further into the zone, the map would fill itself in around the areas you found. For example if you found a town, the area around the town would fill in on the map. In addition you'd also get a few experience points for uncovering that area of the map. So in order to see the entire map, you actually had to go everywhere on the map and doing so netted you a good bit of experience points as well.

Wish they would do this in XIV too.