Minor tweaks I would suggest:
- make monsters (or even better: everyone) ignore scouts so they become useful
- don't show caravans as red (enemy) spots on the mini map, it is disturbing
- add an enchantment that grants a hero "cloud walk" without leveling up air magic
- if an A.I. offers me tribute, I would love to have an option to tell them that I see them as friends and it is not necessary to appease me. That should then count into our relationship as if I had given them the same amount of gildar for tribute.
- a second column for the army/city/quest list would really help
Beyond that, champions still sucked in my game: