I think that they should move closer to their original inspiration for the series; Kings Bounty and Heroes of Might and Magic.
There should be more RPG-elements which allow you to develop your hero and army the way you like. There should be learnable talents, like "Archery commander: +3% to ranged attack for all bow-armed units" and "Folk Hero: -25% cost to recruit from villages" and other kinds of things, alongside the traditional skills. Talents should come in levels 1-3, so while Archery Commander doesn't do much by 1st level, 3rd level should give a worthwhile bonus, by giving 10% accuracy, firing rate and damage bonus to all units and so on. Talents should also have skill requirements; Archery Commander would require x amount of power draw, for instance.
They should also include artifacts; powerful items which give bonuses to skill and other possible features.
Like, for example, the Butter Casket of King Harlaus, which gives you 6 items of butter at the start of every week, and Winged Boots of Escape which give you 75% chance to escape lost battles and the ability to fly over woods, mountains, cliffs, waters and other map-aspects with your army.
Faction variety is also a lackluster thing in M&B, currently. All of them are humans! And they call this a fantasy game? Bah! They should atleast add dwarves, elves, centaurs, orcs, dark elves, dark dwarves, dark centaurs, dark humans and demons! They should also add angels and other celestial and good beings, like gryffons for example, as top-tier units and mounts for the human faction. Dwarves should get rune magic and golem-like construct as special units and mounts, centaurs wouldn't need mounts, elves could get treants and special elfhorses which... are elvish? And orcs should, of course, get goblins and big wolves and goblins on big wolves and goblins in big wolves.
With more, different and unique fantasy factions they should also add new unique campaigns for all of these. By now, we all know that this "sandbox campaign" thing is just an excuse to not be able to come up with actual campaigns! For the humans, the first part of their campaign could be like the one in Warband: Unite all the human kingdoms. Then they should be led in defense against the orcs, demons, dark elves, dark dwarves, dwarves, orcs, elves, centaurs and what not, and then to close the Gates of Hell. This format could be easily used for all the races, and the "close the hell gates" could be turned into "Open the Hell-Gates" for the demons.