During the game you learn various techs that give you insight into the ancient world and given the nature of trade and the will of some human beings to travel it only makes sense that as a nation you'd have rough estimates of the area outside of your own territory and where you've personally explored. Some games like civ offer the ability to trade maps and such for those disinclined to sending scout parties out but I propose a different option.
Faded and inaccurate maps. Currently you have the vivid area around which you can see and the more faded area you've personally explored but are out of view of your units and settlements. Adding an extra layer of possibility would be even more lightly marked maps that can even be wrong outside of the area of your influence or exploration.
If you can find ancient records purposefully hidden revealing a way to take over the world one should be able to find an ancient world map. Now centuries or millennia may have passed and rivers might have changed course and hills might have become mountains and other modifications but you'd at least know the rough outlines of what the world looks like. Besides that you have mountain men and more importantly merchants/traders who brave the wastelands for profits and would be able to tall you something about the lands beyond your control.
With this in mind and the use of exclamation points I promote the idea of using Question Marks. As you progress in your game when you hit certain gildar production levels or research the right Adventure tech or Diplomacy tech you start learning a little about the world around you. Given that you haven't had your units explore it personally you're relying on rumors and spies or the labors of librarians studying antiquity so there is some fuzziness or downright wrong info but if a group of people find diamonds laying on the ground or a motherlode of iron out in the open and bring some of it in to a nearby city people will speculate and stories will spread that there is a iron mine twenty odd tiles to the east thus encouraging you to send some official units to find out.
Then there is also the nature of gossip and rumor at the local inn which would be cool if every once in awhile a popup screen would reveal a new rumor at X inn in one of your cities about X event which may or may not be true.
Such things as a rough idea where the other nations are would be useful question marks. As your knowledge of the world expands you might find out that the Gilden are not sixty tiles to the northeast but fifty tiles to the east but your people provide a rough idea.
Would also work for new temples, mitrallar statues and other such stuff. Have them only pop up solidly in your own visibility map and as question marks outside of your "bright visible area" or "faded questionable area" would encourage more exploration for fun and interesting reasons and less of a reason of simply finding out where the other nations are.
It would also be interesting if once you find another nation's rough location if you could send a sealed diplomatic letter and try to have it reach them in order to send info via multiplayer or encourage them to come find you so you could setup formal foreign relations. Depending on the accuracy of your information it has X% chance of getting there and a chance of being intercepted by rival agents and simply a chance of failure because of the danger inherent in the wilds.
Otherwise I really get annoyed at having to send units out to explore and taking forever to find anyone else. You shouldn't win the game before you find the rest of your opponents.
