The Byzantine Empire
Alexius Comnenus
Alexius I ruled from 1081 until his death in 1118. More than any other individual, he was responsible for the shape and character of the Byzantine Empire that the Crusaders encountered. Byzantium was not exactly in tatters, but it was badly shaken and tottering when he ascended the throne. At his death, it was by no means as strong as it had once been, even a hundred years previously, but it was again on solid ground and a dominant power in the eastern Mediterranean. In the process of recovery, Alexius either initiated or continued changes in government that became permanent attributes of the Empire.
Alexius was a successful general during the reigns of three successive emperors. Particularly after the disaster at Manzikert he proved invaluable, suppressing rebellions and serving with distinction. So successful was he that in 1181 a faction at court offered him the crown, if he could march on the city and take it. This he did, driving Nikephoros III from the throne.
When he took power, Byzantium was facing an invasion by the Normans, led by Robert Guiscard and Bohemond (who later participated in the First Crusade). The invasion achieved early successes and Alexius was hard-pressed. Guiscard had been right: Byzantium was indeed vulnerable; but Alexius was able to bribe others to attack the Normans in Sicily, forcing them to withdraw. The Comneni never forgot nor forgave this invasion (1081-1084).
The rest of the 1080s were spent in battling the Petchnegs, a Turkic people who lived north of the Black Sea but who had expanded into modern Bulgaria and Rumania. After a series of battles, some of which had the Byzantines reeling almost to Constantinople itself, Alexius allied with the Cumans and smashed the Petchnegs at Levounion (in Thrace) in 1091.
The north and the west were now secure, but Anatolia was still in the hands of the Seljuk Turks. This is why it wasn't until the 1090s that Alexius was asking for help from the papacy against the infidel.
Lost in the narrative of the First Crusade is the fact that the Crusader victories in Anatolia allowed Alexius to recover a number of important cities there. And the last twenty years of his reign were comparatively peaceful.