First, medieval tolerence in Middle-Ages is an anachronism.
Tolerence implies that you recognize the validity of one's beliefs even if they are opposed to yours.
What existed, in Christian or Islamic middle-ages was a form of cohabitation or at best what was called
convivenca in occitan (living together).
Now, Catholic Church wasn't the behemoth of power you depict :
- Reconquista was before all things made by temporal power at their likes, and what Rome had to say on it had eventually little matter.
- Crusades are a more defendable cause, but really only for the 2 or 3 first ones. Except for the First and the Fifth, it was directed by kings of Christiendom that acted following their interests, and not along church prescription (explaining partially why they weren't sucessful)
That said, yes, between the XI and XIV, Rome is on a process of reinforcement that, being supported by high nobility itself opposed to greater than theirs, resumed in a mix of christian and feudal features (see below).
Finally, neither Raymond or Pierre of Aragon were overly concerned by Cathars well-being itself (actually, Raymond V tried to tone them down), and the presence of catharism within southern medieval elites was maintained for other factors.
Namely, that little nobles and patrician families had all one of their members at least or converted to catharism or leaning to; and therefore weren't really prone to epure themselves.
Raymond VI and VII eventually supported them more plainly because they were one sure support against french crusaders and french king, and when it wasn't possible anymore, turned their coats again.
2) Secularism in Middle-Ages is another anachronism.
Religious and temporal matters weren't fully separated, and while some temporal rulers could enjoy more freedom in this regard (notably when a religious upper classes didn't had historically a power base in their kingdom such as Sicily), they never get rid of it as their power itself was eventually based on both temporal and religious bases.
----
That said, for the OP
No feudalisation (at least as OTL form) is required, and that's an hell of a PoD.
Allow me to explain myself : the feudal fragmentation of society allowed the rise of a warrior class (aristocracy and knights).
With the strengthening of roman power from one part, and the appearance of religious and popular supported movement as the "Paix de Dieu", it became necessary to compromise christian and feudal ways of life.
The Crusades allowed the sanctification of violance as long it was considered just, aka defending Christiendom.
As heresy became in some parts (Languedoc is best known,
but cathar heresy existed elsewhere) a "rooted" belief (even if it touched only a small minority, essentially in low nobility and urban elites) that went against a process of reinforcement of pontifical authority, they were finally considered as the "ennemy within" for diverse reason.
As said, mix of feudal and christian institutions : pledges, basis of legitimacy of power, and struggle against heresy was a mean of demonstrate his power (Raymond V against Plantagenet claims) and for papacy to have a support among nobility for his reinforcement.
The situation of european Jews followed a similar way (copying/pasting a previous post, where I summarized a doc)
It's a bit long to summarize, but basically : while anti-judaism existed in the Early MA, at the exception of Visigothic Spain [where it was diversly applied], you don't have a strong and continued movement and Jews kept the same status than during Roman Empire (basically, while they had to be maintained firmly in a Christian communauty, inside their own they are free to do).
If the persecution (forced conversion or plunder and/or death) of Imperial Jews during the crusades by disorganized bands (while it didn't existed with the "official" armies) were relativly isolated as well, it was truly percieved by Jews as a degradation of a stable situation that they knew so far depsite the more or less effective protection of Church and Empire.
While the XII century is still an "open" period, the situations began to change with the first mention of ritual murders, as en exemple. While fought by religious and secular authorities (that are still maintaining conversion of Jews as an objective), it was maintained in popular anti-judaism and later in the XIII more or less suported by the beggars orders, representative of a more harsh christian line.
1215 is percieved by the author as an important date, as the Jewish are clearly assimilated to heretics, and to the threat these were supposed to represent for society [let's recall that in MA, religion is the main social referent. Going against or turning away was seen as damaging the communauty as a whole], imposing them discriminatings features [not unlike what existed in Islamic Middle Ages or in earlier Byzantium. It would be interesting to see how the reuse of roman law happening at the same period didn't favoured that]. At this date began to disappear the previous housing that was more mixed (in town as in countryside) with co-existance of both communauties.
While in the XII, Christian scholars (that are divided on this : some support the expulsions and discriminations, other plaid for the former one) tried to read Jewish religious texts openly and "objectivly", these are now burnt. The situation didn't stop to degradate at this point.
In the same time, Jews status change and they are now considered as belonging to a secular authority rather than to their own. To quote the author, the feudal management of Jewish communauties was diverse : "They defend firmly their goods, but when they cease to be useful, you abandon them" at the same time that Jewish communaites began to loose the "political" and economical importance they had earlier.
You really need to
1) Prevent or at the very best soften feudal desintegration
2) Nerf pontifical importance
3) Limit reintroduction of justinian law and identification of Jews as foreign elements for Jews proper.
And you may have a more interesting situation for heretics and Jews, but it wouldn't be nowhere tolerence.