Say Monty's state religion is Judaism, and mine is Taoism. He has one city that's on my borders with only Taoism, and I control the Holy City of the Tao. Shouldn't that city be much more likely to revolt?

It should, dunno if it is. I think it is I am playing a hindu Tokugawa and lived next to Alex (he was christian, I think...), one of his cities quite fast got a 96% Japanese culture, and it had only hinduism...