Another thought I'm having:
Barbarians should go. They don't really correspond ot any historical reality - just to clichés of greco-roman history. But most of the most noticeable barbarian groups of Greco-Roman history have long since been added as one civ or another in the game.
What we should have instead of Barbarians in the old Civ sense is that *everyone* is perceived as a barbarian in the early game. It's only with certain techs and civics, and prolonged contact, that perception shift from barbarians to an identified civilization.
Barbarian civs, and barbarian city states, exist in a state that's neither war nor peace: units can fight (how likely a civ is to be aggressive as barbarians would depend on their settings, etc), but you can have ongoing trade deals with neighboring barbarian cities even while your units are fighting. Trade routes and trade deals would accelerate recognition of a civ as a civilization and moving them outside the Barbarian group. Ideally, you would be able to see their settlement, but maybe not even their names - that would require advancing your communications with that civ (eg, learning their language).
There should be commensurately more city states and cities in the game, to allow for the ones that will invariably be destroyed as Barbarian Encampments in the early stage of the game. Which can also have long-term consquences ("Oh, you were hoping to run into the Jerusalem City State? Too bad, you razed it back when it was a Barbarian Camp...")
We are approaching this from different directions. I've been doing a lot of reading lately on the "Indo-European" migrations, Neolithic Cultures, Horizons and Groups, and archeological evidence for early 'technologies'.
Conclusion: Even if we don't include a Neolithic Pre-Era as
Humankind does, in 4000 BCE there are NO Civilizations or 'states' in the modern sense. Many of the populations that genetically and linguistically will later form the Civs we know aren't even anywhere near their 'starting locations' yet. None of the Indo-European or Turkic languages exist yet, except in Proto forms.
So, every entity on the map in 4000 BCE is, basically, Unknown. Some of them will become Civs, some City States in game terms, some Tribal Huts or 'Barbarian' camps (although anybody who has read any of my posts will know that I want to combine those two into Settlements that can be hostile, neutral, or friendly).
Realistically, you cannot tell who you are going to be playing or what their Unique Attributes are going to be in 4000 BCE. IF you want to play as Greece, you have to cross most of European Russia, pick up Horse Domestication, Bronze Working, and Chariots, develop your amorphous Proto-Indo-European speech into Greek, get Civics/Social Policies like Heirarchy, Honor Oaths and Comitatus, and make your way into the bottom 10% of he Balkan Peninsula - where you will find Old European farmers have already built settlements at Argos and Athens, among other places.
This would make every game something of a 'blind' or Random Start, but you could get 'starting packages' if you really want to play a particular Civ:
Starting Package marshy river valley with wide grasslands all around, heavy hardwood forests to the north nearby, Resources of Horse, Sheep, Cattle and agriculture with Wheat and Korn (all the Bread grains: wheat, millet, rye, barley, oats). You are going to be Indo-Europeans, but where you go from your semi-pastoral start will define you: anywhere from India to Britain and Greece, Poland, Italy/Rome, Germany in between.
Starting Package fertile river valley surrounded by forests and rain forests, Resources agriculture, Rice, Korn, Cattle - if you work at it, you may become China. With Korn, Water Buffalo and Cattle and the same terrain you can work on your Harappan or Indian Civ - eventually.
The completely Blind Start will be a Hard Sell to the average gamer. He wants to play England, damit, even if at the start of the game there are no English, nor Angels, nor Scots nor Norse nor Normans or any of the other groups that eventually make up England. I think the defining terrain, resources, Civics, Technologies that 'push' someone into becoming English versus Scythian can be defined, but it may take some deft programming to make sure the game gives you the right Package to play what you want to play.
And, of course, the Leader will have to be a later addition to your game: in 4000 BCE there are no named Leaders, either. That actually might be a positive twist: somewhere in your development you will have developed the basic Culture and Technology to be Greek, but in that case you will also pretty certainly have the starting attributes to be Macedonian, so you could also get the choice of Leaders: Pericles, Brasidas, Polycrates, Solon - or Phillip or Alexander.