The advantages of NI are well sung. But I prefer PI. Maybe offer a percentage setting but I generally prefer 1-in-10. That way I can still come across provinces that offer hirelings, but not so many that the AI gets carried away with them. Personally I think they also add to the game by providing important provinces to fight over. The reason NI is known more than PI is that PI kills replay on a map so it is best if generted each time. Your program would be great for that.
The only other thing I can think of at the moment is the #ally command which keeps the AIs from attacking each other. Either in teams, or all against the human. Dont remember if you have that in there or not.
If you place the AIs, throwing in extra magic sites on the capital can be a big surprise. Either basic help like more gold, more resources, a sage site.
Or even some major surprises like other nations capital sites which can give an AI nation the elite units of another nation. But then you are getting into my Chaos games. Ever played one?
I have downloadable versions of SemiRandom, PI, and Chaos maps on Dom3Minions if you want to check them out. (the server rerolls them each day for variation)
http://www.dom3minions.com/maps.htm