Another idea that I have is for more remote Christian realms to join the Catholic Church (that is, open relations with Rome). My example would be Spain before the end of the XI century, when bishops were invested spiritually by other bishops (though like in the HRE key royal officials) and the Mozarabic, or Visigothic, Rite was used for religious observances. Alfonso VI of Castilla-Leon (d.1109) encouraged connections with Western Europe, including the Papacy. I understand that Croatia was in a similar situation during the Great Schism, between the Byzantines and the Papacy. And there is the Crown of St. Stephen in Hungary. So maybe some of these regions should start with Orthodox or something similar as the official religion with national decisions to join with the Latin Rite, which could bring the benefit of papal crusades against Pagans or Muslims, special privileges (as inducements to support Rome), and warmer relations with other Catholic realms. This is just an idea that I might mod into my own 1066 game, but I wanted to throw it out there.
The Catholic Church was not and has never been a monolithic institution, even less so because of the slowness of travel and the diversity of local religious practices (particularly in more isolated places or places recently conquered or converted from Islam, paganism, or other forms of Christianity). The HRE, France, and Italy were the core of Catholic orthodoxy (of the papal empire if you will) in the XI century and forward, and it is in these places that IMHO the Papacy paid the most attention. Iberia, Ireland, Scandinavia (as Veld seemed to suggest in response to DD#4), in some cases the Crusader States were the frontiers of Catholicism, and the Papacy tried to help these areas along when possible and in return gained political allegiance and in exchange offered secular leaders a sense of legitimacy. I just thought I'd off up my thoughts for your consideration.