Feudalism was not entirely new to the Middle Ages - it was partially derived from the Ancient Roman system of Patronage [0] between a Patron and Client. So this kind of hierarchical social structure predates the civilizational collapses that led to the Middle Ages. Of course, Mesopotamia predates Ancient Rome, so perhaps it was even more egalitarian. Although slavery has existed since pretty much day one of civilization.
[0] https://en.wikipedia.org/wiki/Patronage_in_ancient_Rome