Here is my version if you are interested in an Alternate-Alternate History;
This Builds Up Towards a Climax that Marks the Beginning of the Game;
In the midst of Viking Raids which plundged Europe into Chaos, Eire managed to unite Politically behind the High King and push forward, uniting the Gaelic Kings of Scotland and expanding over the Isles, their Rulers styled themselves as "High King of the Islands" or "High King of Ireland (&the Scots &the Picts &the Britons)".
Charlemange's Kingdom was likewise divided between his three Sons, however in this world, the Elder Son was Shrewder and Managed to keep the Brothers on edge, both by keeping them wary of eachother and by promoting the power of Barons under them. East Francia fizzled until eventually becoming the Holy Roman Empire as in our World.
Sicily: Rollo makes his conquests in Picardy as in our world, however without a claim to a decent section of the English lands, their attention turns South and they hold on to Sicily much closer in this world; indeed it becomes the centre of the Plantagenet's Throne during the Hundred Years war which ends in the succession of Languedoc, and the united Throne of Sicily, Gascony and Picardy, thus marking the End of France.
Spain; Very Little Change is strictly Necessary, personally though I like the Idea as a fourth Charlemangian Kingdom, Though a Muslim Territory to make up for those lost in the East and Account for a Weaker France makes a lot of Sense as well. I can do a Write up but as you like it.
Other Major Powers; Holy Roman Empire is a major power within Christendom and a strong force of Unity, the Swedish Empire is powerful and has strong ties to the other Viking Kingdoms of Normandy, Finland and Denmark
Now, the East is where the Major Changes Happen;
The Mongol Hordes hit harder and consolidate better than in our world, rather than less so, even if they never gain a conqueror quite like Gengis again;
The Middle Eastern Caliphates and Powers Collapse under the Mongol Hordes, allowing a campaign of reconquest for Byzantium and the Burgundy-Normand-Mongol Alliance [Historically the French-Mongol Alliance Floundered] is declared a ressounding Success as the Kingdom of Jerusalem is founded.
Similarly, the Rus narrowly resist an invasion which is aimed towards the North in this history, The Rus do not manage to form a single state in the wake of this but rather unite behind the Nations of Novogorod, Moscovy and the Ukraine, with the Ukraine quickly rising to be the power of the three.
Without the pressure of Northern Russia, the Polish-Lithuanian Commonwealth stays strong and helps to maintain the strength of the Jagellion Dynasty in Hungary against the Hapsburgs [who may or may not be a Power in Spain].
Finally the Protestant Reformation arrives and in the wake of this History's Thirty Years War; The Swedish Empire and Normandy are the Major Powers against the Catholic Armies of Poland, Ireland & Hungary. A Catholic Victory exacts harsh terms over the Protestant Nations, ending with the Independance of Finland, Picardy, Gascony, Wessex, Yorkshire [Northumberland], Holstein, and All Southern Baltic Territories.
However, inspite of this, the Holy Roman Empire does not remain in a happy union. Protestant States and Populace are bitter about their return to this union, neutral princes are treated bitterly by the rest of the Nobility and so on. It is not long then, until under the weight of tension, the Emperor is assassinated and the HRE is deadlocked for picking a successor, eventually leading many to talk of succession.
The HRE crumbled and the power to the North Collapsed, Germany and Northern Italy open up to their ambitious neighbours who have long envied their lands march in. This of course sends shock waves over Europe as the Ukrainians, Irish, Spanish, Israelis and Romans lean over to see what they can grab as Europe is once more thrown into Chaos.