Traditionally, "Civilization" meant "Cities" and that's the concept around which Sid and his successors have built an entire game franchise - and an Extremely Successful one at that. But the very dichotomy between 'Civilization' and Others is now suspect, since technological, cultural, and political sophistication does not require cities at all, and so the basic interaction between City and Civilization, although still linguistically present, is not so evident in historical or archeological reality.
1. The game is devoted to the scale of civilization building. Except that it is a very sliding scale, ranging from founding cities to building individual granaries and farms, from decades-long trade route interactions to individual fights between spearmen and archers. In other words, the 'scale' ranges from relatively small groups of men and periods of a few hours to centuries. To speak of 'scale' in the game is meaningless. Focus of the game, on the other hand, is relevant, but again focusing on building cities to build a Civilization is a false dichotomy, and even in that focus one ranges from city, religion, technology and cultural developments to the actions of individual artists and governors - Great Ones, but still individuals in the supposedly Civ-wide population.
2. All the attempts at 'prehistoric' starts and eras in Civ 5 and other Civ versions were automatically imperfect, because they made the same distinction that the basic game makes, assuming that the 'Pre-Era' includes no city or settlement building IRL and little or no cultural, religious, or 'civic' development. Humankind's 'Neolithic Start' just barely avoids that trap: you can place settlements ("outposts') in the Neolithic, you can build up population, but you cannot develop any distinctive cultural attributes or technologies or expand any 'settlements' into Cities, so they only get it about half right.
3. The earliest agriculture was not, we now know, limited to the Levant. At the moment the earliest evidence of 'neolithic agriculture' is from a site near Kermanshah, Iran dated to about 9800 BCE, while the earliest evidence in the Levant is of cultivated figs at Jericho around 9400 BCE. In the 'four corners' of southwestern North America between 9000 and 8000 BCE there is evidence of potato (jamesi type) being specially prepared as food: whether it was completely 'gathered' or cultivated is still debated, but given that they developed specialized pottery containers and cookware for it, it seems like too much effort for something you are hoping to find rather than planting where you can get it regularly.
In addition to agriculture of any kind, food animals like pigs, sheep and goats (10000 - 9000 BCE) and cattle (8500 BCE) were all domesticated for food, and the earliest locations are also scattered: pigs in the Levant and separately in China, sheep/goats in the Levant and Iran, and cattle in northwestern India. Also, we tend to overlook the immense amount of food obtained from water or marsh: fowling and fishing provided enough food to feed good-sized permanent settlements, and even off-shore whaling was practiced as far back as 6000 BCE (Korea) and 5000 BCE (Scandinavia).
As for cities themselves, they predate the 4000 BCE Start of Game, also in several locations:
Jericho (Levant/Palestine) - by 8400 - 8300 BCE was a walled city of 40,000 square meters with a population estimated as 2500 - 3000, Neolithic stone tools, but cultivated wheat, figs, sheep and pigs for food.
Motza (modern name) - near modern Jerusalem, by 7000 BCE had estimated 2000 - 3000 people, farmed wheat, barley, lentils, and traded with Egypt and Anatolia for Obsidian and seashells (amenity/production goods!). Two 'trading partners' were Nevali Cori (modern name) near Gobekli Tepe in Anatolia, which by 8000 BCE has the earliest DNA evidence for cultivated einkorn wheat, and Asikh Hoyuk (modern name) in central Anatolia, estimated 2000 + people, an obsidian source.
Catal Huyok in Anatolia had an estimated 5-7000 people by 6500 - 6000 BCE and may have done the earliest metal smelting - lead - before 6000 BCE.
In China, the Pengtoushan culture in the central Yangtze region between 9000 - 7500 BCE had the first permanent settlements in China, evidence of cultivated rice by 8200 BCE. The Dadiwan culture to the northwest in China by 7900 - 7500 BCE had earliest evidence of cultivated millet, and ceremonial architecture: raised earth platforms supporting at least one building 4500 square feet in size.
Seskla (modern name) in Thessaly, northern Greece, had an estimated 5000 people by 5000 BCE, cultivated wheat and barley, domesticated cattle, sheep, goats, pigs and dogs, had glazed, decorated pottery
Mehrgahr (modern name) in Pakistan, between 7000 and 5500 BCE one of the earliest agricultural sites in south Asia, cultivated barley, wheat, earliest DNA and archeological evidence (post holes for pens and corrals) of domesticated cattle
And just taking our 'historic' Civs, note that the first five cities in Sumer all date from just before 4000 BCE, while another 'historic' city, Ugarit on the Mediterranean coast, dates back to at least 6000 BCE, by which time it already was fortified with stone city walls.
In short, there was a lot going on pre-4000 BCE in more than one part of the world, and I haven't even touched on the technological developments, that in the period 10000 - 4000 BCE include Animal Domestication, Agriculture, Irrigation, Stone-working, glazed and decorated Pottery (and note, the Potter's Wheel dates to at least 1000 years before 4000 BCE), Boating (paddles, not sails or oars), Wine-making (and trading), and Metal-Working (in silver, gold, copper and lead).
Now, most of this activity cannot be related to a straightforward linear Tech Tree or the type of directed development the Civ game has used for years: whether a simple settlement developed into a centrally-directed City with heirarchy and ceremony and 'government' was really dependent on the terrain and resources available and the ease with which resources could be exploited and developed. Basically, I think the Eureka system could become the major source of tech development until you get a city with all the 'trimmings' - ceremonial buildings, religious structures/shrines, and a leadership people will pay attention to - basically, something to hold the city population together when things get tough (numerous early cities, Catal Hyok being a prime example, were simply abandoned when drought or other negative factors hit them).
Those developments, by the way, are as much related to Civic/Social Policy-type development as Technological development: there were several ways to feed a city (animals, cultivated plants, fish, waterfowl, etc) but without the concept of Heirarchy (someone in charge who is not just the senior family member) and some kind of 'government' (tribal council, senior Priest, God King) the city remains a collection of families and cannot be led and developed the way Civ expects cities to develop.
The game, then, could have a 'Take Off' point where the city/settlement develops enough 'city characteristics' to start having the regular Tech Tree and Civic developments 'kick in' and the normal game begins - but that point, like the advance to the first regular Era in Humankind. would not be fixed: you could be wandering or living in small settlements for quite some time if you don't have access to the exploitable resources or reason to develop any further technically or socially.
Also this may be how to include colonial nations seamlessly - though sadly it reduces the number of civs around. It however can be an easy buff for earlier civs when introducing new leaders. Simon Bolivar open ups options for the Inca AND the Spanish - or maybe he‘s really good with the Japanese in the free for all mode. 
