I enjoyed Sorcerer King a lot, but something I recall wishing could be improved -- and now hope will be improved in Rivals -- was the limited use of magic at the strategic level by the SK and enemy factions... They never (or extremely rarely?) cast overland spells against me or cast summons or unit buffs on their stacks outside of combat. Not that I observed, at any rate.
I would love it if approaching the stronghold of the SK or a city occupied by some enemy heroes, they'd rain down fire on me, some nasty stuff like that. I feel that if this were improved it would make the mid-late game a lot less predictable, and obviously tougher.
In another game that I am also very fond of, The Age of Wonders, the ai players cast spells globally all the time when they've got the mana, and won't hesitate to smoke my uber stacks to oblivion with a couple of storm spells. I'd like to see that happen in SK:Rivals.