I came to think of one particular thing that keeps repeating itself in most strategy games (like GC2) and which actually makes the early to mid game predictable, and the end game sometimes just boring. It is basically that the pecking order among the civs for going to war and when is always the same (due to the AI). When a civ starts getting really powerful militarily and economically what happens is that all the weaker civs are sure to leave it alone since it would be suicide to attack on your own. At the same time the strong civ always attacks the weakest civ and crushes it, then takes the next in line etc. While the others idly stand by, whimpering, awaiting their own doom.
Compare with a game of Risk and it plays completely differently. As soon as one player starts getting powerful the other players will increase their attacks, but most of all they will try and team up against the threat. This is one of the most interesting aspects of the game since it means earlier promises are broken, new promises/lies or made, new alliances are forged etc. This is the stage where some players starts arguing and really hate each other (only in the game, hopefully, although not always the case ...)
I think Elemental could learn from it, and should include some kind of mechanism, probably through diplomacy but maybe also helped by magic, quests, items and hero interventions, in order to allow weaker civs to both do something against rising threats without committing certain suicide, and also teaming up.
For example, instead of only having the option to ask civ x to declare war on civ y (which the AI always refuses in cases like above) there could be an option to team up against civ x. This could also be linked wider to alignment (option to propose that all good civs go against the big evil one), to religion (all of the true faith go against the heretics), to race (all humans against the fallen) etc.
It's not only about all out war though. As important would be to have the option for example to team up against someone strategically (say through a secret treaty) meaning you do what you can to stop a certain civ from prospering: cutting trade, cancelling any positive treaties, refuse to trade or give resources, refuse access to territory, intensify spying activity incl offensive actions, if possible: attack caravans, make skirmish attacks etc.
A good spy system would help a lot in letting weaker civs take some action against more powerful civs, hurting them without necessarily ending up alone at war against them.
Also random events could affect the development, for example making all civs of a certain race more eager to go to war against the biggest due to an event, etc. Since this is mostly based on chance it should not be decisive though.
Another part of the solution would of course be to include such reasoning in the AI, if this is possible through Frogboy's magic ... But some diplomatic options for the player would be very nice in any case.