It is not the rulers that are the problem that would cause the fractures within the co-existence - Kings and reasonable authority figures are pure opportunists when it comes to religion - one day they might be pagan to sway the masses, the next they might be Christian -- IRL Constantine - his conversion was a political move not a religious one. He wanted to have enemy soldiers defect to his army instead of fighting in the service of his enemies.
Kings have been known to drop religion, take it up again, and use it when it serves their interests - Wars of the Reformation, "Paris is worth a mass," etc.
They are only one half of the problem - the other problem is the priesthood.
All a Christian priest has to do is cite the first four Commandments to his flock and say, "Our king (or reasonable authority figure) is not following the law set down by god, therefore we do not have pay taxes to him" and step back and watch the chaos come down onto the king (or reasonable authority figure).As soon as you say "do not have any other gods", you basically closed the gate to any form of tolerance and co-existence - anyone that suggests it is labeled a heretic and heretics have been known to burn quite nicely at the stake.
If you do not believe me try to build a mosque next door to a Southern Baptist Church in the Deep South of the US - there will be no love from the pulpits; as for the reasonable authority figure (mayor, governor, senator, representative, president), he (or she) will play both sides down the middle and in the end, he (or she) will side with whatever has the highest poll numbers and contributed to his (or her) re-election.