This sounds so much like something that have already been done (in Civ4 for example) that I'm unsure of the real impact it would have, as it has very little impact (flavorfully at least) by the past.
As long it is only a starting choice with no other changes extending from that choice, it is almost worthless in a game of Civ's scope. The point I'm trying to make is that the Starting Position on the map, the resources and terrain available, the starting technologies that come out of that, fundamentally change the way your civilization will develop, at least for the first third to half of the game.
For example, if you start on a plain with a river and herd animals as a starting resource AND choose Animal Husbandry as your starting technology, the Applications for Animal Husbandry include include Leatherworking, Composite Materials (leather, bone, horn), Animal Breeding, and Exotic Domestication. You can research any of these in about half the time you could research another 'regular' technology. Leather Working will lead you to Leather Armor (upgrade to any early troop-type), Composite Materials will lead to Mounted Archery, Animal Breeding will lead to Horseback Riding, Exotic Domestication will allow you to utilize Elephants or Camels if they are available.
You could, of course, try researching Agriculture and converting to a 'standard' current-civ-type technology advance, but you would actually be going backwards: Agriculture as a standard Technology will take you twice as long to research as any of your Applications, and your Applications will lead more rapidly towards units and technologies more immediately useful to your particular civilization. No single choice change will make a great difference in a game of the scope of Civilization, but a choice that leads to other strategic choices can change your development for a good part of the game, and that's the kind of 'differentiation' I'm looking for.
Should we start way before 4000 BC, or having several types of civs to choose from (with the different techs), or having no civ choice and adapt as soon as we settle the first city ?
No need to start before 4000 BC, as long as the game recognizes that by 4000 BCE civilizations and groups had already differentiated to some degree, based on their surroundings. Thus, some civ will already have developed Agriculture, others concentrating on Animal Husbandry, and still others have already taken to the Sea (island start, coastal start with islands visible off-shore).
I foresee two ways to start the game. First, you could start Traditionally (the way the game always has until now), You pick a Civilization, possibly with a specific Leader. Example: you pick Carthage. In that case, you WILL get an Historical Start Position: your Settler will be on the coast, the starting radius you can exploit will include some kind of Grain/Fish or Animal, and you will have a list of Starting Unique Attributes from which you can choose. These will include General Attributes based on your Starting Location, and Civilization-Specific Attributes. For Carthage, these might include:
Barbarians are 33% more willing to Trade than Fight
Barbarians and City States are 33% more willing to Hire their Units to you as Mercenaries
Research Exotic Domestics 50% faster as soon as you get access by trade or exploitable radius to either Camel or Elephant resource.
Note that these are designed to give Carthage access to some of its signature Uniques: trade routes and influence with Barbarians and City States (Trade Empire), armies of Foreign Mercenaries, and Elephant units. The ability to move over Mountains is, frankly, drivel: Hannibal tried it once, lost all his elephants doing it, never tried it again.
Having a coastal start, Carthage could choose a Starting Tech of Boating, which allows sea trade along the coast, a primitive coastal ship (Pentekonter?) and non-mounted military or civilian units to move through coastal tiles - to exploit island resources or establish Trading Posts/resource-exploiting Camps down the coast. However, having a coastal start will make researching that Technology much faster than if they started inland, so you could also start with Agriculture to build a fat city on the coast, do fast research of Boating to start trading down the coast, and Exotic Domestics to access Camels and start Trading Routes across the desert. Obviously, that last choice requires a desert and trading partners, but it shows the possible "Carthaginian Strategies" which the Historical Start Position gives you.
The other start technique is what I partially described in the previous Post: you start with, for instance, a basic choice of Starting Position: Jungle, Plains, Desert, Forest, Coast, Island. You open the game, see the actual resources in the Starting Radius, and pick a Starting Technology and General Attribute. The Civilopedia will give you hints as to what Civilization your choices will be tending you toward, and a choice of starting City Names based on those hints.
Example: You choose a Coastal start, open the game and discover your Settler is on the coast, with hills, Grain, Olives, Fish and islands visible offshore. Your choices for a starting Technology are Agriculture or Boating, because you do not have any herd animals to exploit as a Pastoral culture. You choose either one, and the Civilopedia will point out that your starting position is compatible with Greece, Carthage, Phoenicia (or however many other variants of Civs the Civ VI programmers decide to include). That choice will give you access to Starting Uniques, or you could choose not to choose, and accept the General Starting Uniques and see what develops later.
The Applications of Agriculture are Irrigation, Terracing, Forest Cultivation, and Lunar Calendar,
of Boating they include Advanced Woodworking, Stargazing (primitive Navigation with Religious Applications), and Weaving (Nets, Sails)
Whichever you choose will obviously lead you in somewhat different directions down the Tech Tree, assuming you make a rational attempt to Maximize your research effectiveness from the start.
(can nomads make armies ? I think they are not numerous enough for that, unless we invent something totally new, but would it still be History related ? We could give it a try i guess (after all, well, Giant Death Robots...), especially if we lack of faction types, or just abandon it) Or, even if they are doomed, why not simulate them anyway ? They would be a factor of population and interaction on the map at start. And, if you are isolated, you could even reach the modern era with high techs ?
That first question is a joke, right? The answer is Yes, in the languages of the Scythians, Persians, Ottoman Turks, Huns, Hsung-Nu, Mongols, Alans, Magyars, and all the other Nomadic Armies that conquered or harassed the Hell out of their settled neighbors. Nomads chasing herds, even massive herds like the North mercian bison, are not particularly numerous; nomads with semi-domesticated herds of their own can be quite numerous, and more importantly, the requirements to protect those herds from predators two and four-legged makes every adult male (and many of the females) of the nomadic society a dangerous warrior, with riding, archery, javelin-throwing or lancing skills that require specialized training for their settled counterparts.
Historically, though, purely nomadic groups were all eventually stomped by their settled neighbors who both outnumbered them and got access to technologies that provided gunpowder weapons: the horse archer is a devastating opponent who can wound from 200 meters away until he faces an enemy with a black powder rifle who can knock him off his horse dead at 300 meters and outnumbers him 5 to 1. The successful ones took over their settled neighbors, like the Persians took Mesopotamia, the Turks the settled middle-east (after being invited in as mercenaries!), the Mongols the Chinese Empire. This gave each of them access to the 'settled' technologies and the manpower base to continue to be competitive. That's the transition you have to make if you chose to start as a Pastoral civilization, but how is it different from the choices you have to make now, playing as the Huns in Civ V? All of your advantages are Front-Loaded: if you have not conquered your way to prominence by the Middle Ages, enemy Knights will ride down your Horse Archers, enemy Pikemen will crush your Battering Rams, and you will get soundly whipped.
if you don't win being a pastoral civ at the apogee of its power, you may be too short technically (although I wish there are ways to recover fast), but also culturally, adopting the way of life of your enemies, being absorbed by them... (or becoming them ? how would that work ?)
See above for the historical answer. In Game Terms, I suggest that conquering a city would give you access to some or all of the Technologies discovered by that city's Parent Civ, and holding a city as a pastoral Civ would start giving you discounts on researching Technologies related to non-pastoral cultures/civilizations. This would, I think, allow the gamer to try replicating the historical Ottoman/Persian/Mongol successes in a game, and avoiding the historical Hun/Lakotah/Alan failures.