How about this - decrease the conversion resistance of the pagan religions? Make pagan counties that border christian counties spontaneously convert. Remove the 100% ability of the ruler to (choose to) imprison a missionary. That way paganism would be a real race against time - you NEED to reform. This could also tie in perfectly with the viking raid
This, 1000 times this. The problem with raiding isn't the raiders. The problem with raiding is that the start in 769 makes it very unlikely to have the pagans convert in a reasonable amount of time. In my perfect CK timeline:
769-850 Charlemagne's Empire - Initial setup converts to "future" setup. Have titles that expire in some way (So more "West Francia" in 975) so that running these huge empires becomes a race against a clock of "I need to form France by 900 or my empire will start to fall apart!". Best suggestion: Titles that are significantly beyond their historical timeframe have ticking increases in "independence" faction revolts designed to bring the empire down. Also, titles have limits of when they can be created or usurped. So in theory, a Karling King of Middle Francia that has his only kingdom title disintegrating around him will eventually be a 1 province count that gets annexed by a larger realm.
850-1066 Viking Era - raiders like crazy. Once this era starts, the AI gets a flag telling them that the best way to stop the raiders is to convert them. I know once the raiding starts I send my Court Chaplain out to convert pagans like crazy. Also included should be "Christian creep" where counties border monotheistic religions.
1066-1453 Rise and Fall of Empires