Since EUIV and the change to the power point system, there is only one holdover from the old "wait x months" style from previous games, and that's missionaries. I believe that currently there is no downside (other than possible revolts) from sending missionaries to convert provinces, so everyone does and everyone tries to convert all their provinces to their religion, and you can usually do this in a few decades.
Historically speaking, countries took hundreds of years to become religiously homogeneous and this effort took valuable resources away from other pursuits that were quite honestly more worthwhile. I would like to propose the following:
Remove the Missionary system, instead people spend both ADM and MIL power to convert provinces, the same amount that you would need to spend to core said province (unmodified) from both ADM and MIL, so for a 2 tax base province, 40 ADM and 40 MIL, and it takes as long as culture change does. In exchange, the economic penalties for wrong religion are removed entirely, but the revolt risk and religious unity penalties to stability remain in place. I would actually argue that wrong culture economic penalties should also be removed but a "cultural unity" penalty to stability be added for every non-accepted culture province.
Owning Mecca or other holy places should give extra legitimacy (+0.1) instead of additional missionaries. Missionary Schools and Spanish/Holy traditions should both lower the cost to convert Heathens by 20% (so Spain with Missionary Schools can convert heathens for 40% off). The Inquisition idea gives a 20% discount in converting Heretics. Inquisitor advisers give an additional 10% discount against both heretics and heathens.
Some religions are harder to convert, for instance Muslims and Christians have a 100% conversion cost against other religious groups, due to the treatment of apostasy. Unorganized religions like the north American pagan religions have a -40% discount. So the same aforementioned Spanish can convert an 8 base tax Aztec province for 32 ADM/32 MIL, but to convert an 8 base tax Dutch province costs 320 ADM / 320 MIL.
Religious Zeal would add an additional 100% penalty (so if the aforementioned Dutch province is newly Reformed, make that 640 ADM / 640 MIL).
I would also like to propose that any nation can request that another nation convert to their religion, if they are in the same religious group. This request is easier the more provinces they have that are your religion, how strong you are compared to them base tax and militarily, whether you have an alliance, royal marriage, are a vassal or in a personal union with you etc.
The bonus on converting to a Protestant denomination would give a 60% discount on converting Heretic provinces (so if you also have religious ideas and an Inquisitor, possibly 90% off conversion costs until it expires).
This proposal would balance the current situation. Right now there is very little incentive not to just convert everything. With this change, going for Humanist ideas for that 25% religious unity bonus to tolerate your sizeable heretic population would be more worthwhile than trying to convert them.
De Heretico Comburendo Act, Advancement of Religion Act, etc should instead of adding missionary strength, instead increase the tolerance of own religion by +1.
