A point thats been mentioned elsewhere a bit too (havent they all though), is somehow slowing down the rate at which the world can be explored and mapped overall in Civ. Only in fairly recent history overall have we finally explored and charted the whole world with accuracy.
So, here are some ideas to better simulate these limitations. Units and explorers face greater challenges to health and longevity the further from your borders they attempt to travel. There are perils to traveling through wilderness...lack of water or food, diseases, wild animals, bandits attacking (well, barbarians covers this maybe). I think that in the earlier ages it would be very difficult to explore far before your unit died or was killed, and that it probably shouldnt be your military units doing the exploring. I mean, who sent out a legion of troops to explore? You send out parties of explorers with light armament probably. And the early world would be an inhospitable place to wanderers.
Stretches of desert or ocean or deep forests and other inhibiting terrain types would be difficult or impossible to get through until later techs enabled further and safer travel, even much later in some cases (like with Navigation). Finding trade routes to build between nations (a daunting task taking longer than before) would be important and maybe difficult for quite a while. Roads should be expensive through wilderness.
Explorers would move perhaps two tiles at a time in early times which no other unit except a horseman or chariot in the open could do, and would be vulnerable to the above mentioned many perils. They might even have expiration dates. An explorer can only move through X tiles of wilderness once leaving an established city, and would likely die of starvation, disease, old age, or other causes even before that. However, explorers should be allowed to reset if they can reach a city of another nation where they would restock and regain health, assuming the nation lets them into its borders. If not, the unit would likely die in the wilderness.
Military units need supply routes to keep from degrading as mentioned in other proposals. You wouldnt send a troop of spearmen wandering off into the jungles, forests, deserts, or mountains. They would degrade and become useless as military units and be easy prey to disease, barbarians, and other threats like explorers. Military units are for protecting cities, for marching down securable highways to invade your neighbors, and occupying fortress outposts, etc. where they maintain their supplied strength. But back to explorers and mapping...
In earliest times, mountains cannot be crossed by any units nor a road built thereon. You might find a pass through or a way around, but it might take numerous exploring attempts to get that far. Mapping obviously would take a long time, but the game would encourage you to really focus on tightly building and improving your first few cities early on rather than rapidly expanding all over the map as fast as you could. If barbarians, diseases, enemies, corruption, or the rate of being able to road or build settlers was sufficiently daunting, you wouldnt be practically able to spread out too far from your capitol for quite a while early on. Early civs would start very localized for somet time, and might even be boxed in ultimately by surrounding terrain. Its simply hard to map very far from your own lands for a long time, and you really might not meet many of your neighbors for a while longer than at present typically...certainly not directly any more. Youd get information or diplomatic connections with them from your neighbors in more of a chain fashion.
Rivers would carry boats and act as natural roads, pehaps as in Civ II. A river through the mountains in early times is a great way to get through to the other side before roads can be built affordably in mountains. Perhaps roads through mountains are just very expensive and time-consuming early on, so it can be done, but at great sacrifice to resources needed to maintain and grow your young empire. Roads shouldnt be an imporovement pillaged by barbarians or enemies any more. I mean, how often does anyone really destroy 33 miles of road? Rather, military units block and occupy them to cut off supply lines and trade routes. If an enemy parks a military unit on your road in the mountain pass, they have blocked your supply route over that mountain from your capitol to whatever lies on the other side...a city, a trade route, your supply of iron. Bridges should be a terrain improvement which could be pillaged for similar effect however, forcing you to rebuild it which takes time.
The early rates of expansion and settlement would overall be a lot slower, as settlers too should face greater challenges and risks. Later on, as tech improves and more national contact has occurred, maps get better, explorers are more hardy and able, settlers get where they are going more often, terrain can be penetrated more deeply, and so forth. I love the exploration and settlement phase of the game. This should be extended much further into the game as it was in the real world instead of being an Oklahoma land rush.