What would you change in Heroes of Might and Magic IV?

It's terribly unfortunate that you can't generate random maps (or maybe you can).

You can, if you figure out how to use Heroes IV Map Enchanter v.3.4 ;) Random maps tend to be lifeless, but there are many maps online where the authors have put their heart and creative ideas into them.