It would be nice if there was story generator for every sandbox games. Let me explain:
Imagine a TBS game based in a fantasy setting. All "players" are the human race. They can only build cities in open lands.. etc.. They all have their characteristic and specialty.
But, spread all around the map, there are non-human races, randomly set. In some forest, there is an elf city. Dwarves in mountain, wastelands crawl with orcs, etc.. "Elves" are just mightily powerful, but they keep to themselves. Don't go into their forest, however! Civilization built near them can try to befriend them, try to learn from them (for magical technologies), or even launch massive armies to try to conquer them.
Dwarves are in unreachable mountain. It's just plain impossible to conquer them. But they can be good trade partner, they have their own trade goods, and they could join war.. etc.. Civs built near them would have better-than-average weaponry, but it would cost them.. etc..
Orc simply spawn in wastelands, and attack, attack, attack. The civilization near them would have to become more martial. Their armies, however, would have a lot of experience.
You could also have some precursor superpowerful magical theocracies, who demand tribute to everybody. Eventually, you will have to rally a huge rebellion to free your civs. Etc...
blablabla.. You impliment some kind of.. landscape in the game. Now, imagine a GalCiv2's way of doing this.
Every game should be different, off course. The best example I can think of is Babylon 5: the species have to deal with a universe who is the battlefield of 2 super-powerful races. Extremely advanced, and they use less-developped empires as pawn in their big games.
Or I even remember what the Minbari ambassador told to the terrans in "Babylon 5 : The Beggining": "In all our travels, we went everywhere. But we NEVER upset the Min'Bari". Why not having an empire who keep to himself at the middle of the galaxy, simply centuries ahead technologicaly? Every ship who come near their world is simply destroyed, no question or explanation asked... But except them, they are just.. there.. until a civ become powerful ennough to try to conquer them, and capture highly-advanced technology.
The possibilities are infinite. Why make a simple "sandbox" game that is always the same, when you could.. I don't know, add a little flavor to the whole galaxy with other species. The "regular" species would still be the only race playable, and the only one allowed to win...