During my years of playing heroes i must say that H2 has some unforgiving A.I.
Like when it sends out some decoy-hero with crapitems that you get when he is defeated (i e you get that bill that costs 250/day or fisbin of misfortune). Now in h3 that whould not do so much as it be only a to move it to the inventory. Perhaps a decoyhero with a zillion banners could suffice in h3 due its mechanics. Brainstorming needed on just this one…
Maybe say thieves for example could get some skill based on chance to steal an item from heroes inventory (random item). Now lets say the heroes runs around with a set and one of the item gets stolen and that thieving hero retreats, that whould kinda ruin the day. 
Or when A.I. sends forward a hero mere to nume you with armageddon (hit ´n run) or even those cooler kamikazeheroes with that use armageddon. I´m not suggestion giving the A.I. superpowers beyond what can be achieved normal. Just “human” dirty-tricks.
Perhaps someway of letting the A.I realize when a human have a tankhero that cant be beaten and instead of trying to beat that hero it concentrated on scattering its resources to thieving towns, mines, driving for economic superiority (like we humans do when we realize the computer has a single superarmy). Or if A.I. gets townportal that it whould use a armychannel-hero. That is a dedicating that hero to TP all around accumulating armies (like we do to them).
Now I know I´m much into programming etc. But i bet some of these feature could be implement with some comparasion. Some perhaps just on/off/random/semirandom naghtyness.