[Fantomen]

Flying thugs can work well if you make a lot of them and have them attack rear on different turns. Make sure to have some regular fliers attack before them.

Flying tramplers are good too, like elephants/behemoths/leviathans buffed with gift of flight or big guys with stymphalian wings+golden shield, I like GORed seige golems or crushers for that.

Well placed and protected mages are sure hard to kill though, but thats a good thing IMO.