It's not strictly the Muslims who are too strong, it's
a) the ridiculous duchy-level Holy War that can be spammed for 50 piety, as if every lowly Emir in history had the religious or worldly authority to instigate such a war - or the intention to conquer all his neighbours;
b) the Fatimids being far too stable at the beginning of the game, as has been said on these boards over and over again, for good reason;
c) after a failed Crusade, the dynastic decadence of the Crusade target dropping to a solid zero;
d) the Holy Roman Empire, or France, or the Fatimids, or every huge and (historically) quite disorganized nation being able to raise large levies for the conquest of Tunis, and ship them to North Africa without any problems, and also being able to defend their fancy new overseas possessions with 10000 troops afterwards;
e) the Normans in Naples and Sicily being much too weak initially.
Iberia is tricky - sometimes it's a fun brawl, sometimes it's Muslims all over the place in 1130, only to be beaten back by France and the Empire; more rarely it's Christians finishing the Reconquista in a few decades. The Taifas should be weaker, but the Almoravids stronger (and more inclined to grab land in Iberia). Also, I have never seen Portugal form on its own, mostly because the duke of Portucale never goes for Independence when he revolts (and boy does he revolt often!).
