excommunicate entire nations
Ok, there's a major misconception here. I think you're blurring the line between how the game models something and things occurred in reality.
Excommunication simply means that the person in question can't receive holy communion or take an active part in Mass, but they are still expected to attend and to perform other religious duties expected of them (fasting, tithes, etc).
Also, the Pope did not excommunicate entire nations of people. Rather, they excommunicated individuals, specifically Kings who defied papal authority or committed some other sin that merited them for excommunication. Just check out this list and see how many major figures in Catholic Europe were penalized, a few being some of our very own leader heads:
http://en.wikipedia.org/wiki/List_of_people_excommunicated_by_the_Roman_Catholic_Church
I don't know how the Excommunication option in the AP currently works, but if it permanently removes a member from voting then that is inaccurate. The point of excommunicating a person is to incite them to change their behavior so that they can return to full communion with the Church and receive the sacraments again.
So I propose, if it's not this way already, that a successful excommunication vote simply bar the offender from voting in 1-2 AP elections, to represent that leader of that nation would eventually be forgiven and welcomed back (as the list shows, some rulers were multiple offenders and were pardoned almost every time).
There's also a huge difference between the power of the Pope on paper and the power in practice.
While the Pope had a huge influence on all of Europe, he was still reliant on the other nations deciding not to march in to Rome and oppose him, excommunication and Swiss mercenaries being his main defense. He was influential, but he didn't have total control over every aspect of life in Europe. If he did, then things like the Hundred Years War between France & England and the Reformation would never have happened. He never even unified Italy, which was divided for the whole middle ages and beyond, and there were rivalries between Rome and the city states for centuries. There's a reason the Pope isn't as powerful today as he was in the Middle ages, but even that's stretching it.
As for the Hagia Sophia, the AP, and switching Orthodoxy & Catholicsm, here's my take:
-Orthodoxy can spawn first, in Jerusalem/city of whichever civ gets Theology first.
-Hagia Sophia a buildable Orthodox wonder, it should halve the amount of temples needed for a cathedral rather than only needing one temple. This effect can benefit the owner regardless of religion.
-AP either buildable by any Orthodox civ or spawns automatically in Rome at some point (probably around 1050). If the Papal States are added, then AP simply spawns with their birth in Rome.