How about a Frankish Empire where the Carolingians abandoned partible inheritance?
Charlemagne leaves his empire to Louis The Pious (Louis I) but Louis leaves the Empire in the hands of only one of his three sons.
Say the Carolingians (and their successor dynasties) eventually conquer the whole of the Iberian peninsula, the Italian peninsula, central Europe and the Baltic. Maybe they conquer Britain as well and forge a strong centralized empire along dynastic lines that eventually rules over the whole of western Europe, including Scandinavia, where they first learn of lands to the west, through the viking sagas.
Eventually, Constantinople falls and new routes to the far east are needed.
The reigning emperor has two choices: Try and conquer the east and retake the old Byzantine Empire or look for another route. By the time Constantinople falls, Maderia, The Azores and Canary Islands have been discovered.
Are we to assume Henry the Navigator just becomes some complacent noble just because he's not a king? Doubtful, men of such curiosity will always seek to satisfy such curiosity, be it within their means or through sponsors.
Perhaps Henry finances the initial expeditions (Or in this world embarks upon them himself!) which yield the fruits of discovery and the possibility of new lands for the Empire. Perhaps the Emperor decides that there may be more to gain through exploration than through a costly and bloody war against the Turks.
The Emperor has to keep his options open on the eastern front, but Henry's discoveries and this "Vinland" he's read about have peaked his interest. He sponsors more voyages, south, along the African coast at first, opening up sea lanes to the far east there, but eventually, Columbus is going to show up in his court and propose a passage to the east by sailing west. The Emperor takes a chance on an expedition and Columbus delivers to him a "New World".
There's billions of things that could go wrong in a timeline like this, that spans so many centuries and so much history. Maybe the Frankish Empire never makes it that far, bogged down and defeated by the Moors in Iberia, or in the frozen north or the Baltic region after which a slow decline and rampant infighting eventually tear the whole empire appart.
But if they survive into the Age of Discovery, they'd be THE colonial power, as far as Europe's concerned.
It'd make for an interesting story though: Templars or Teutonic Knights taking the role of the Conquistadores, discovering the strange new civilizations of Meso and South America, the great explorers competing with one and other for the Emperor's favor (and funding) or perhaps finding private investors and commercial interests to bankroll their voyages and colonies.
If there's a Reformation (and there probably would be) the wars that went with them could end up being waged all over the globe, with "Reformist Colonies" and "Imperial Colonies" setting up alliances with the indigenous peoples of the different colonial hot spots.