What I envision is a game world divided into multiple realms - say 5 or 6 to begin with. Each realm has a capital city that serves as a fixed point from which people can spread out to populate the realm. The Capital City, while static, culd be occupied by an enemy realm, but the physical city could never be completely removed the way a player created city could be.
The Capital City starts off as little more than a fortified keep, where the king and a few other key NPCs reside. It is up to the players to build the rest of the world. At first, this means clearing land and building basic houses, planting fields and setting up a village. From there, players can spread out across the land to found new cities and advance their realm. What I would incorporate is elements of RTS games and games like Civilization or Sim City. There would be a definite technological progression, from relatively primitive wood, stone and mud construction up to the techonlogy levels of the Roman Empire or Renaissance Europe. Perhaps there would be magic, too, if you want to go the fantasy route.
As the game progresses, cities would be built, with roads and shipping lanes connecting them. Eventually, realms would come into contact with one another. Perhaps the contact is peaceful, with the realms trading for mutual benefit, sharing technology and wealth. Perhaps there is war, and the border lands are fortified and raids common. However, one realm might fall victim to another entirely, and be overrun.