Well, I didn't say that Egypt was. However, we do have an estimate that by about 3400 BC, the population of Hierakonpolis was at about 510,000. The registers of the Palermo stone indicate a succession of at least 9 pre-dynastic kings of Ombos before the registers switch to the pre-dynastic kings of Hierakonpolis. We estimate to about 3600 BC for the beginning of kingship at Ombos.
Eridu as a city only dates from about 3800 BC with an estimated population tipping 10,000. (Wright 1981:325) Let's not confuse the date of establishment with the date when that establishment became a city. Babylon, for instance was only a village about 2300 BC, but didn't become a city until about 1900 BC.
al-'Ubaid was not even as large as Eridu which was the largest site of the Ubaid Culture. Why do you refer to it as "first empire"? Cultural expansion in this case didn't mean "political expansion". The kind of tell-tale artefacts we look for to even come close to such a conclusion is remains of fortresses with exclusive cultural artefacts from the home country, outside the land of origin. Instead all we find is Ubaid pottery spread over a large area of the Middle East in conjunction to the artefacts of the local cultures. In this case we speak of "imported" or "imitated" pottery, since it was with the Ubaidians that a primitive form of the potter's wheel was first invented.