What a cool question. I can't tell you anything about dates and when things were founded that you couldn't get off Wikipedia, and you've obviously done a bit of your own research, which is good to see. As you can see by my flair, this also isn't my field. What you are asking is as much archaeology and anthropology as it is history. But I will try and give you something worth reading nonetheless.

I'd distinguish between buildings and collections of settlements marking an established community, even a small city, and more developed settlements we tend to refer to as city-states. It is city-states, with their political, economic, religious and perhaps military structures that we might think of as our first "civilisations" with "true" cities. History begins with writing, which dates back to c. 3100 BC with Sumer, but symbols that were the precursors of such writing date back to c. 8000 BC (Keegan 115). Evidence of economic activity dates as far back to evidence of shepherding in northern Iraq c. 9000 BC (123). But agricultural settlements are a different thing, dating back perhaps to Jericho as you have said, where 2000-3000 people might have lived as far back as 7000 BC (124). Around the same period but a little later, a city in Asia Minor has been excavated of double that size. Irrigation economies did not come about in Mesopotamia and later Egypt and India until 3000 BC, but thanks to Jericho and its walls we can see that "agriculture, urban life, long-distance trade, hierarchical society and warfare" had begun thousands of years beforehand (125). Farming villages also existed in Europe as early as 8000 BC, and urban settlements existed on Crete and parts of Greece c. 6000 BC, and settlements were even coming together in Britain (125). However, our first hard evidence of warfare, and history in general, is with the Sumerians.

The Sumerians are argued by Keegan to have built the first cities by about 3000 BC which could be called "city-states", which were primarily theocratic and agricultural (128). Keegan's reason for claiming that the Sumerians built the first cities is due to the advantages of Mesopotamia, laying between the Euphrates and the Tigris, which allowed settlers to develop a new level of irrigation and agricultural sophistication (126-7). They began by developing "small, self-sufficient communities" that co-operated with each other due to the mechanics of irrigation and the fact that the rivers changed their beds, and this co-operation eventually fell under the purview of a priestly class, who therefore became the political as well as religious authorities due to their economic power (127). The temples became administrative centres, they developed the capacity to organise labour and centralise resources. Sumer also developed the capacity for long-range trade, and around the same time similar irrigation societies were growing up or gestating along the Nile and the Indus, though the Chinese/Indo-Chinese had not yet developed this far (128). It is this centralisation and organisation that leads Keegan to call them the world's first true cities.

Fortified towns are supposed to have existed from the fourth millennium BC in this area, and the Sumerian city-states are known to have engaged in organised warfare in the third millenium BC, with a particularly prominent development being the creation of the world's first Empire under Sargon of Akkad c. 2300 BC (Guilaine & Zammit 195). A centralised state had emerged in Egypt from 3000 BC also, with corresponding improvements in military organisation (125). However, depictions of warfare date back to the mid 3000's BC (1).

The most curious thing is that, as you pointed out in your original post, Jericho (and Catal Huyuk in Asia Minor) did have defences as far back as c. 7000 BC, with Jericho in particular have a continuous wall ten feet thick at the base and thirteen feet high and 700 yards in circumference, complete with a moat and towers, built of stone (124). So clearly warfare was an issue back much further than the 3000s BC. However, the enemies Jericho's walls were built to defend against may have been raiders wishing to plunder stored produce rather than any seriously organised opposition (139).

So basically, we had cities well before Sumer. But Sumer was the first evidence we have of something resembling a "state", with city-states that actually were combined under central authority for a time with Sargon of Akkad. If we take Keegan's word for it (and I would), the development of central administration and government and the capacity to organise labour and resources, and defend them if necessary, only really came about with the Sumerians. The development of irrigation economies in Mesopotamia appears to be a key element of this economic and societal development. The extent to which the Sumerian city-states could centralise, control and utilise their resources and engage in organised warfare and diplomacy seems to be far beyond anything comparable in the preceding millenia, even Jericho. If you want to put it in terms of population, the world's population increased from 5-10 million in 10,000 BC to around 100 million in 3000 BC, when these irrigation economies were developed (Keegan 125). It was only Sumer's irrigation economies that provided the surplus resources to stimulate significant population increases in a small area, and competition for those resources. At the risk of grossly simplifying the issue, I suppose I'd say that the development of irrigation economies with Sumer is when civilisation as we can track and recognise it really got started.

Sources:

Guilaine & Zammit, (trans. Melanie Hersey) The Origins of War: Violence in Prehistory, 2001/2005.

Keegan, A History of Warfare, 1993.

Postscriptum: /u/Hurin88 and /u/ Hergrim quite rightly question the use of Keegan as my source on this matter, as Keegan is not an anthropologist, archaeologist, or ancient historian. However, Keegan was keenly aware of his limitations in this matter and up-front about it, and I think his analysis is basic enough to be of use here. Of course, like Keegan I have a biased perspective in that as a student of warfare I tend to associate organised warfare with "civilisation", funnily enough. However, a more informed user on this subject in the shape of /u/missingpuzzle has provided more subject-specific information on dates and city formations that everybody should look at.