I am hardly qualified to address a question over all western Europe over a millenium (I suspect that's what you meant but you didn't mention it explicitly), but I think I can address it reasonably well with England, specifically three kings there.

One king was practically out of a fantasy trilogy. He had been a barbarian mercenary in a far land, he had led large war bands maurauding, he battled for thrones.

One king ... if the word "feudal" applies anywhere, it applies to him and the realm he grew to manhood in. Possession of a castle was crucial to control and safety. Government there was, but it was mostly private, authority given by becoming the "man" (homage) of a stronger man and promising faithfulness (fealty), receiving land of the lord. Knights in armor. A realm where the king's power really extended over only the core of his lands; by far most of that realm was controlled by great lords who took little notice of his theoretical authority.

One king held a strong and unified England. Government was fairly sophisticated. Law was royal. The courts were royal (though local magnates were often enough in charge by royal appointment or grant). The officials, civil and church, were appointed by and subject to the king. The king could tax the realm. The king raised the army -- private combat was nearly unknown. There was a royal council, but it did not bind the king.

That was not a survey of English government from the earliest Angles and Saxons to Henry VIII.

That was a survey of England from Monday through Thursday of the fourth week of September in 1066.

So I cheated a bit. The first guy was never king of England, just king of Norway, and all he got of English land was 6 feet of it, or as much more as he was taller than other men. (Which he was.) I was proleptic with the second guy: it took him two more weeks to win the crown. "A realm" actaully referred to his homeland of France, not to England. And I may have exaggerated the power of the English monarchy for the third man, but I don't think by much.

A few hundred miles to the southeast was a man claiming to be heir of the Caesars and absolute ruler over Europe, though his real power was much more restricted and limited. (Cool fact: he, or his heirs not long after, had ministeriales, major royal ministers and lords who were unfree.) If you didn't like that Caesar, you could find another one a few hundred miles further on with a much different government. I think the Italian city-state republics (south of Caesar #1) didn't kick off for another century. And don't forget the Moors -- it's not like they detached Spain from Europe.

So even considering just Europe (as I assume you meant), even in not long a span of time, there was a wide range of theoretical and effective governmental power -- I write under correction, but I don't think it's accurate to say that there was one type of government in the western European middle ages.