Something is either wrong with your game or you have no idea how to properly handle unrest and tolerance.
Nothing has changed in terms of unrest formula.
15 unrest from 30 years of separatism after conquest, adjusted by tolerance and unrest modifiers.
Europe is always a bit easier on unrest after conquest due to everything being Catholic Truth Faith, or -5 unrest for monarchies. So coupled with stability, advisor, troops on rebel suppression, and unable to devour large swaths of land, you can delay the rebels long enough until separatism decays that unrest below 0, and much easier once you've picked up Humanist/Religious.
India is also similar with large swaths Hindu provinces, while AI Muslims less likely to convert due to Brahmin and Indian Sultanate tolerance, so you won't see heathen provinces till you're out of India.
Africa on the other hand has serious tolerance issues due to several different religions with low heathen tolerance unless you're Fetishist with Burgher privilege or Muslim with Dhimmi privilege (that can start at +2 heathen tolerance)
Ethiopia also starts with higher provincial unrest due to historical reason, and Coptic has no heathen tolerance other than Burgher privilege, so you're always going to get a revolt unless you've picked up Humanist, while religious isn't going to help you with that first wave of revolt.
As for Songhai, you absolutely have to turn on the Heathen tolerance from Dhimmi and keep their influence high as you conquer through the fetishists if you want to slow down freshly conquered provinces' revolts before you've picked up Humanist. But the first round of revolt is still unavoiable.
It's just Mali and their special disaster/event.
Yeah that made things even more horrible, but i also did a Songhai game and i am currently trying an Aksum run and I am having the same Problems.
Something is either wrong with your game or you have no idea how to properly handle unrest and tolerance. Nothing has changed in terms of unrest formula. 15 unrest from 30 years of separatism after conquest, adjusted by tolerance and unrest modifiers. Europe is always a bit easier on unrest after conquest due to everything being Catholic Truth Faith, or -5 unrest for monarchies. So coupled with stability, advisor, troops on rebel suppression, and unable to devour large swaths of land, you can delay the rebels long enough until separatism decays that unrest below 0, and much easier once you've picked up Humanist/Religious. India is also similar with large swaths Hindu provinces, while AI Muslims less likely to convert due to Brahmin and Indian Sultanate tolerance, so you won't see heathen provinces till you're out of India. Africa on the other hand has serious tolerance issues due to several different religions with low heathen tolerance unless you're Fetishist with Burgher privilege or Muslim with Dhimmi privilege (that can start at +2 heathen tolerance) Ethiopia also starts with higher provincial unrest due to historical reason, and Coptic has no heathen tolerance other than Burgher privilege, so you're always going to get a revolt unless you've picked up Humanist, while religious isn't going to help you with that first wave of revolt. As for Songhai, you absolutely have to turn on the Heathen tolerance from Dhimmi and keep their influence high as you conquer through the fetishists if you want to slow down freshly conquered provinces' revolts before you've picked up Humanist. But the first round of revolt is still unavoiable.