A thought or two inspired by part of this comment seen via /r/bestof, said part being:
Where it gets extremely tricky and sensitive is how non-fundamentalist Muslims fit into the picture. The same for non-fundamentalist Christians, or Jews. Because the fundamentalists would argue, and in a way I agree with them, that the beliefs of these people are so far removed from the original message and meaning of the religion that they are not truly Muslims, or Christians or Jews. In order to achieve a form of Islam, or Christianity, or Judaism that is acceptable to ‘Western society’, you have to reshape and twist the doctrine of that religion SO MUCH that it can start to not make sense at all.
(You may also want to read the surrounding paragraphs for context, but I don’t think you really need to.)
…and which, in the finest spirit of “everything gets used for worldbuilding”, I shall now use to illustrate something of the nature of non-native religiosity in the Empire and one particularly characteristic problem people run into at immigration.
‘Cause here’s the thing.
The Empire is an unabashed ideostate, neither an ethnostate nor a volumetric geostate. It is the contractual association of the Freest of the Free, which certainly anyone is permitted to join – the advertised immigration policy is, after all, “just turn up” – but they do have to be able to sign the associative contract in good faith. Like so:
I, affirmer’s full name and/or identifier, hereby affirm my agreement and attachment to the principles of the Fundamental Contract; that all sophonts are endowed with certain absolute and inalienable rights; that these rights are to life and property, liberty, and the pursuit of eudaimonia; that all sophonts are equal in their exercise and retention of these rights, without privilege or priority; that sophonts cooperate amongst themselves in separate and coadunate action to secure them; and that they do so freely and by their own sovereign will.
Therefore, as a free and self-sovereign sophont of recognized competence, I hereby agree, consent and reaffirm my binding to the rights and obligations of the Fundamental Contract which underlies the civilization of the Empire, on my own behalf as well as that of my guardianship; consenting to be guided first in my actions by the Rights of Domain, of Defense, of Common Defense, and of Fair Contract; and accepting freely the obligations attached thereto to guard the absolute and inalienable rights of my fellow sophonts as my own; and in full understanding that should I Default from this, my own rights shall therefore be abeyed until the default is amended.
Given under my hand this day date,
Witnessed this day by witness’s full name and/or identifier, who, as a citizen-shareholder in good standing of the Empire and an adherent of the Contract, pledges surety in the light of the Flame for the competence of the signatory and the validity of this Affirmation.
In good faith, for these purposes, implies “under alethiometric analysis”. Which is a problem, if you believe in the fundamental doctrines of many religions, ’cause however in good faith you may feel you’re being because obviously such considerations couldn’t possibly be meant to apply when you’re quarter-valuing women, abominating homosexuals, or stoning those buggers who wear mixed fabrics, your mental reservations will light the alethiometer up like a Christmas tree.
(We pause briefly while the House of Exemplars pats itself on the back for its collective foresight, inasmuch as everyone from Merriéle Herself  on down to the present day were careful to note that they were just writing down their best perception of what the eikones wanted and expected ongoing contemplation and future generations to revise accordingly with the benefit of further thought – and thus avoided binding their seven-millennia-later successors to a bunch of Bronze Age mandates labeled the ineffable, eternal, unchangeable TRVTH. Dodged a bullet there, eh?)
But here’s the catch-22. There are also a lot of non-fundamentalist people around who would pass that test, because they don’t literally believe in the aforementioned things, but they’ve never really repudiated them either. They exist in the shadowy doctrine-twisting world in which, sure, this is the ineffable word of God and the scriptural basis for our religion, except that it obviously doesn’t mean what it says and what He really wants is peace, love, charity, fluffy bunnies, and other things more in accord with modern thinking that don’t explicitly punch the Contract in the face.
…yeah, that won’t get you in either. Because regardless of how self-aware you are about it, that is going to light up the alethiometer with the information that you, sir, ma’am, herm, or neut, are someone who espouses Serious Philosophical Commitments to Ideals and then ignores said Ideals for some stuff you and your chums just made up, belike.
That doesn’t play very well with people who take notions like “obligation” and “self-integrity” and so forth seriously. And it plays even less well with the Imperial Guard of Borders and Volumes – being the people asking you to affirm a Serious Philosophical Commitment to an Ideal – who will bounce you and your admittance request right back out the door and onto the next starship to Hypocrisia.
Which leaves as admissible only those whose ancient theogonists happened to luck out and hit enlightened libertism – or at least values that don’t gratuitously offend enlightened libertism – by chance or revelation, or else those religions flexible enough to engage in theologically supported reform as they go. (There are more than a few Christian sects that would qualify under this clause, because what they believe and what they espouse are aligned with each other, and that theological and doctrinal evolution were intended; equally, of course, there are more than a few that wouldn’t.)
The combination of these effects leads to both a tendency to cooperative niceness where non-native religiosity is concerned, and to many-much vigorous denouncing from outworlders. But then, they’re used to that .
 Whose own writings reflect a certain willingness to argue with the divine, and indeed to look Heaven in the eye and judge right back. The Church of the Flame followed  in this initial tradition.
 The ripple effect this has had on ecumenicalism and religious diplomacy by producing a religion whose representatives, while more than happy to go along with civilized polyhenotheism, also have no problem whatsoever with saying out loud the equivalent of “Man, your god’s kind of a giant celestial asshat, huh?”, is left as an exercise for the reader.
 A standard cadet exercise at the Stratarchy of Warrior Philosophy is constructing memes to get the people denouncing them on the extranet for being tolerant and the people denouncing them on the extranet for being intolerant (of the intolerant) flaming each other instead. This is both good introductory-level practice and kind of funny, so.