What a lot of people don't seem to realise is that it's not the AI that is getting worse, it's the game that keeps getting more complex. As BjornB just said, the AI is continuously improving, but it's just not enough to keep up with increasing game complexity. It's not fundamentally worse, it's just performing worse within a more complex environment. It's all perception.
Now that that's been said, I wonder how much longer is it going to take for you to realise that if you started playing MP instead of complaining that the AI offers no challenge, you'd actually start enjoying yourselves.
I beg to differ. It is true the environment is more complex but in W1 AI GM were much more challenging. They sometimes expanded to as many as 20 cities and could eventually conquer the wild areas by luck, persistence and force of numbers. They produced a ton of units and waged war persistently. That was their main problem and as several people, including me, pointed out the AI could have been serious opposition to a human on impossible ... if they all ganged up and attacked together instead of fighting each other. Essentially the difficulty of SP games in W1 could have been ramped up enormously simply by adding a big bias in diplomacy for the AIs to make peace among themselves and pick fights with the human player, effectively dogpiling as it is called in other games. Unfortunately this was never done. But the W2 GM need a lot more than that diplomatic help, they need serious bonuses to things I will cover below. Most other strategy games give the AI very big bonuses on the top difficulty level and Warlock can follow on that path.
In W2 the AI does not seem to get beyond founding 5 cities now and so doesn't get to use the huge advantage it has in gold (is it X4 on Impossible difficulty?) by producing loads of units like it used to. When I run over their capital after killing their units faster than they can build them they often have 5000 gold! They do buy the gold perks for their units and when a unit gets killed the perks are recycled it seems. But the weak expansion means they don't get many resources for perks so that is limited. Also I don't think I've noticed any spell perks on units, so that is an area that it can be improved.
I think the easiest way to make the W2 AI more competitive is not to simply give the GMs even more gold or mana, it can't spend what it has already. The AI GM need more perks right form the start. I think adding a few extra of the non economic perks could make their troops tougher and giving them some good starting damage spells would make them perform better. So on Challenging give the AI 20 starting perks and on Impossible 30 starting perks

If all their troops start with Koatl Training, Instructor and Glorious Tactician they will be a lot better at dealing with the wild areas and conquer the neutral cities.
Simply double the starting City limits for Impossible difficulty from 5 to 10 and do the same for perks from resources, just double the amounts, so they get 10 perks from 1 iron resource and so on. Increasing the limits will be a lot easier than trying to get the AI to deal with them like human players do.
Special cities are not used at all by the GMs. The gold and mana special cities are not needed as that aspect is mostly covered by the bonuses they get already but if the AI could aggressively settle fortresses they could present a much more formidable opposition.
I am sure there are other bonuses that could be given to the AI to bolster their fighting ability, like free temple units every 10 turns after turn 50 say but let's see if any of the changes I suggested above make a difference. I am not sure if any of these things can be put into a mod but if the developers don't do something like this I would be interested in playing an impossible version of the game that really was (nearly) impossible.
JJ