The aforementioned timeframe is 769-1453. I'm aware that's a very broad period of history- for that case I think it would be best to break it down into 769-867, 867-1066 and 1066-1453 as those periods would differ from each other. I know that coalitions did occur sometimes, but how common were they, and how large were they? I doubt personally they were much larger than regional, but I'd be interested to learn more!
For context, "coalition" in Paradox games means a diplomatic structure designed entirely to protect against and fight against a specific other nation, usually one who has been conquering too quickly or blatantly for their neighbors' taste.
It's not just an alliance, those are different.
The most obvious example that comes to mind is the fate of the Hohenstaufen dynasty, a powerful imperial dynasty that, with Frederick II, combined indirect rule of Germany and northern Italy with direct rule of the Kingdom of Sicily (Naples and points south). Frederick II famously paid little heed of the Papacy (excommunicated on four different occasions) and, between his unsanctioned Crusading and his neglect of his lands in the Holy Roman Empire and his blatant disdain for the Papacy, managed to form a list of enemies including the Papacy and the leading German and Northern Italian magnates. In the generation following his death, the Hohenstaufens lost not only the Empire, but the Papacy sanctioned Charles of Anjou (a fascinating figure in his own right https://en.wikipedia.org/wiki/Charles_I_of_Naples) to come in and seize the throne of Sicily, which he did, and did everything possible to ensure that the Kingdom of Sicily and the Holy Roman Imperial throne would never be united under the same crown again. (A Hohenstaufen princess married into the Aragonese royal family and justified Aragon stealing Sicily away from Charles of Anjou, leaving him with just Naples).
Europe in the High Middle Ages by William Chester Jordan talks quite a bit about Frederick II's rise and fall.
I think the most famous medieval alliance (leaving out the crusades, of course) was between Scotland and France begun in 1295. (The Old Alliance, as it is affectionately called by Scots.) Obviously, this alliance was against England. Scotland wanted to remain a soverign state and France wanted the English out of France completely (while much of their territory had been lost they retained Gascony). Later with the Hundred Years War it obviously had continuing uses. It only broke up in the 1560s
One famous example is that during the Hundred Years War Edward III made alliances with some German powers and the Low Countries to join him against France. Although those German alliances weren't particularly useful and were very expensive the Low Countries definitely had some use.
The English and French also fought a proxy war in Castille over a dispute over the throne. This meant that the English sided with one claimant (Peter) and the French another (Henry). Which is a coalition of sorts. (That was about 1366.)
In 1385, there was a civil war of sorts in Portugal. With the English intervening and taking the side of a bastard born claimant John against the King of Castille. (The English hold grudges.) With the help of the English the Portuguese won. That was an English-Portuguese alliance. Also, sort of a derivative of the Hundred Years War. It's not that those are the only alliances but I'm just stronger in English history.
The Italian city states were always forming alliances with each other but also with other countries. I think it was a lot more common than you'd think.
The League of Lombard and the Hanseatic League are two famous examples of coalitions formed by city-states to counter greater, threatening powers, whether it was the Holy Roman Empire attempting to asserts its authority over Italy or Denmark and the Vikings in the Baltic region.