The game should start with the entire map geography revealed. 

First, the cloth map is beautiful and covering it up for the majority of the game is a crime.

Second, it gives the player a reasonable understanding of where they are in the world.  Which allows the player to better formulate a strategy for expansion, and place their opponents geographically.

Third, it could be applied to provide a cinematic start of the game, where the camera starts pulled back to the cloth map and tracks and zooms until it's focused in on your sov, standing alone in the wastes (which I think would be awesome).

Edit:  I need to clarify...

This is what you see when you use the cheats to remove Fog of War. 

Everything.  All the monsters, all opponent units, cities and ZoC, all goodies, all quests, resources, everything.

Now imagine this map without the labels, lines, and units.  Like it's just a map.  No quests, no monsters, no resources, just the map.  Rivers, mountains, oceans, forests and that's it.  When I say "reveal the map", that's what I am talking about.

You still need to explore to find resources, monsters, and your opponents.

(I posted this idea as a reply in the 100 turns of AI thread, but I think it deserves it's own subject line.)