Have the mapmakers ever considered mods to spice these up? Maybe drop it back a few levels(prince to monarch) and give the AI all of the traits. You could edit the XML values so the AI don't play like themselves also (a mansa/shaka hybrid?).
On top of an evil map and sidequests, that could spice things up a bit. Dropping the level may encourage new players. Immortal probably scares off some people.
We used a special Mod for the game at least once before, but it involved only a very minor change to account for the scenario (I think it forced the fallout to stay until cleaned rather than randomly start disappearing)... or some such minor change.
We try to cater to the philosophy of "unaltered gameplay" as much as possible, while exploring variety of settings and man-made obstacles to overcome. Besides, staff here are mapmakers primarily, not modders.
Anyhow, I think "Unrestricted Leaders" with "Random Personalities" probably comes close to your suggestion, without needing a MOD. Or am I misunderstanding you?