The AP is the most powerful wonder in the entire game. It lets trash play win the game. I would be proof of it, since without it, I don't go past prince. That's also kind of why I leave it on.
I have no idea what they were smoking when they made it. An early game wonder that is essentially "I win". Why bother planning a tech path, micromanage your cities, and time your attacks when you can just herp-a-derp a win?
The only surefire way is to build the AP, and switch to an obscure religion just as it is finished (helps if there's a golden age) and then rejoin the lovefest.
That's why I go for it myself but I understand that's not always possible. I suppose it's possible to lose to it through bad luck in this case but I've never seen it after I've learned the mechanics.
Alarm bells always need to go off when you hear Christianity got founded. Immediately assess the religious situation and join the side you will win.
However.....
If you feel that you will not be the most loved of this bloc, it's also in your best interest to keep heathens alive. These will often be your path of resistance. So if you don't think you'll be voted for, then the strength of any rival blocks will help you.
Consider you have a neighboring Gandhi that nobody likes. He's Buddhist all by himself, and you hear Theology researched by 500 BC. This is bad. It would be highly beneficial for you to keep him alive because if he builds the AP, then it's unlikely he will be able to AP cheese. If he's not, then it's possible that none of the future AP religion will go into his cities. (If it does,. you can "fix" it by capturing it). What else can help is if you acquire theology yourself, and trade it to them too. Having theocracy is also a great way to stop being "infected" by unwanted religions.
I understand this goes against conventional logic, but it really is the best way if the AP goes to another bloc if you can't control the best one.
It also gives more prerogative to keep people alive instead of wiping them completely. Isabella, a zealot, with her 2 cities you left for her in the tundra may be your last bastion of defense.
Also do your best to prop up whoever is their rival if you're not yourself. This includes voting for them , and spreading religion as needed.
I understand that it may have not helped in that particular situation but I feel these things will help the AP work with, not against you in the future.
As a truly desperate measure, if your map has any islands, you may attempt to form a colony that won't have the religion.
However, in most cases, you don't have to panic. Even if this all fails and they are loved, they still need 75% of the vote, which is a lot of votes, so work hard to keep it down somehow.
In the end, this thing is unfair. No doubt about it. But for me, there's only 3 options. You control, the AP, a weakling controls it, or it gets burned down.
EDIT: Just did this on Monarch Pangea. Feels good!
I actually ragequit this on my first try because Brennus settled literally in front of my capital in 2400 BC and I couldn't go anywhere.
This game features Qin building the AP and a buddhist lovefest with me having 5 cities.... in 1500 AD and no academies. That HA attack didn't go that well; Brennus was dead but I wasn't too well. I'm not even big enough to be considered a candidate but I am big enough to block any victories. So the only weak diplomatic target is Fredrick who I've been trading somewhat but he only has 1 city close by.... and runs the risk of Gil flipping all my conquests. But it's okay. I have Cuirassers and they don't. That's all that really matters.Also, Ragnar was a recent convert. We were already on good terms even with different religions thanks to mutual struggles and tributes so spreading the religion to him would make him a important ally.
Fredrick gets killed off (I wouldn't vassal him anyways, and things get much simpler when I sign Defensive pacts with my non-opponents, and also stuffed everything involving health/happiness in my cities. Missionaries were hastily made to spread the religion because this wasn't going to last. At least the cultures and the theaters could hold some culture down.
What did you know, they wanted me to win anyways.
I really didn't deserve to win this, and I was lucky there were 3 AIs that liked HR, but hey!