If you turn on debug you can see how much trouble the game goes thru trying to place many nations on small maps. The variables are extensive.
The SemiRand program is one of the things designed to fix the bad gods problem. The pretender, scales, dominion level, etc are better. (or at least as good as a human player altho it could still use some help from players in choosing better for AI)
The AI difficulty level is mostly just how many points it has to create the pretender and choose scales. You can turn off cheat-check but that still doenst give you extra build points. But you can text a file that builds better pretenders and scales with more points than you would be allowed to use, then attach them to a map.
Here is one of the threads discussing other AI improvements.
http://forum.shrapnelgames.com/showthread.php?t=44783