That's enormously far from truth. Christian Church and state were two separate institutions from the onset.
Maybe it started that way, but it sure didn't remain that way. I'm actually reading a book right now about the Tudor period in England by Jasper Ridley, which notes that "one of the duties of a king was to decide what religion his subjects should adopt and issue orders from time to time telling them exactly what they should believe about religion and exactly how they should worship", and that this was the reason why "[w]hen there was a Catholic sovereign, [the bishops, noblemen, and justices of the peace] could supervise the burning of Protestant martyrs; then, when the King changed his policy, or was succeeded by a new King who made England Protestant and suppressed the Pope's supporters, the mayors and JPs could arrest and torture the Papists, and revert once again to burning Protestants if a Catholic sovereign came to the throne."
Which, of course, is exactly what happened under the alternating reigns of Henry VIII and his children.
That said, with the exception of Vatican (a state formed solely for the purpose of having the Pope of Rome subject of no man) today is secular. Every single Muslim state is either Islamic, or on a path towards becoming one.
Countries like England and Norway have an established state church where the sovereign is the head of the religion, while Bangladesh has secularism an explicit part of its Constitution.
What you describe as "tolerance" is more accurately described as "subjugated second class citizen".
As the Bernard Lewis (who metacristi loves to quote) put it in
What Went Wrong?,
"In the world of Islam, governments might discriminate against non-Muslims, including Jews; but they rarely persecuted them. There might be contempt, degradation, even occasional repression, but there was nothing in Islam to compare with the specific hatred, both theoretical and popular, that was directed against the Jews in Christendom."
Is it? Orthodox Greeks were the majority population of the entire Asia Minor, until the highly tolerant Seljuk Turks arrived and cleansed them from their homes. Constantinople was the largest and most important city of the orthodox Greeks, until it was conquered and ethnically cleansed by the highly tolerant Ottomans. The lands between Sinai peninsula and the Atlantic ocean were predominantly Christian, until the highly tolerant Arabs conquered the lands and made them into second class citizens in their own lands. The highly tolerant Sultans of Andalusia in Cordoba placed Jews into high positions, until they highly tolerantly massacred them so they wouldn't amass too much power. Malta was depopulated and remained almost unsettled for two centuries when the highly tolerant Muslim invaders took the island in 870.
It wasn't "ethnic cleansing". The Islamic conquerors incorporated the peoples they conquered into their empire (and, for the first few centuries of Islam, even
discouraged any of them from converting to Islam), while it was always the practice of Christian Europeans to completely wipe out members of other religions (just compare how many pagans were left in the Baltic after the
Northern Crusades with how many Jews and Christians remained in Iberia after the Islamic conquests there).
That's why Islamic Spain had such huge minorities of Christians and Jews, while after the Reconquista every single Muslim and Jew was expelled or killed, or why Greece under the Ottomans still had a mostly Orthodox population but expelled every single Muslim and destroyed all the mosques post-indpendence, or why Egypt today, 1500 years after it became Muslim still has a larger percentage of Christians among its population than any Western country including France has Muslims.