You can fight some of the other Christian Civ's. Sometimes you do it and it gets the pope mad; often, it doesn't. Remember you get Pope's favor by doing things like building temples and the like. Some of the cities don't formerly ahve the religion -- move your missionary in, and you get Pope's favor.
There are a few ways to play this. You can ignore Pope's favor and just try to beat everyone up. You can try to win by getting the pope's favor up and ignoring verything else. (Note,this is actually too easy. You can essentially bribe a victory. Just don't do that and it is fun , and as you saw, it can be easy to mainuplate.)
In most cases, you will be situational -- try to see who the Pope doesn't like, beat them up, but sometimes they are too far away and the like. The Byzantines and Saladin are almost always fair game and get Pope's favor.
I haven't played as Charlemagne, he seems to spawn the relic. It is in one of his cities. He moves it around quite a bit, I often find I have to take Charley out completely to get the relic.
Best wishes,
Breunor