I'm afraid that I can't agree with the premise of your question, that before the fall of the (Western half) of the Roman Empire "few seems to embrace the practice of one person with absolute power."
On the contrary, monarchy was the norm in the Ancient World. The examples of democracy in some of the Greek city-states, Athens being the most famous example, and in the Roman Republic that preceded rule by Emperors were definitely outliers. The Sumerians, Egyptians, Babylonians, Assyrians, Hittites, Israelites, and Persians were all ruled by monarchies. Macedonia was ruled by a monarchy and, as such, the successor states of Alexander the Great were all monarchies. The Etruscans were ruled by kings (in reaction to which the Romans chose a semi-democratic form of government after they gained their independence from the Etruscans). The two most powerful states between the first century A.D. and the fifth century - the Roman and Persian Empires - were monarchies.
It's true that the Celtic and Germanic 'barbarians' were not initially ruled by kings. However, the different Germanic peoples who inherited the territories of the Western half of the Roman Empire were, at least by the fifth century, if not earlier, ruled by kings. Why and how this transformation within Germanic society took place is far from clear. Some scholars have suggested that the demands of migration, usually involving warfare, led to the concentration of power in the hands of war leaders at the expense of the power of others within Germanic societies. Another factor may have been the example set by the Roman Emperors which Germanic leaders, who inherited populations of Roman citizens governed by Roman bureaucrats, chose to emulate.
In any case, during the Middle Ages (a thousand year period that involved all of Europe and the Middle East), as you've noted, monarchy was also the norm. But this was merely a continuation of the practices of the Ancient Period of history that preceded it.