From what i've been reading, everyone wants a more advanced version of the AI from Maj1, more diverse constructions, the ability for heroes to form actual parties(instead of just wandering around together like in Maj1), heroes who actually get visual upgrades and can get upgraded in ranks.
Also, everyone here seems to be focused on only Maj1, Maj2, and other Simulation games. Personally, i think Paradox needs to take a look at the Stronghold series, as the AI for the villagers is pretty good most times, as well as the mentioned Total War series for its territory-to-territory stuff. if heroes would be wandering from the screen your kingdom is on, the devs would need to rethink the Majesty series's big map entirely. From Rangers, this would allow messages back to your kingdom about encroaching armies of monsters or heroes, a "War" mechanic per se.
For the suggestion about parties, both heroes only and henchmen led by heroes, what we would need would be a building similar to the Champion's Guild, where heroes with affinity with each other(say they accidently hunted the same target once) could meet and form a party to go and hunt down a high Attack Bounty target thats been sitting around for awhile. Of course, hiring henchmen would work similar.
As has been mentioned so far, the biggest pull of Majesty, and most simulation games about cities/kingdoms, is the people actually being able to "think" and act on their own. A virtuous "Warrior", is likely to go to an inn for a breather from his adventures, but if he sees a minotaur attacking a nearby hut, he should change targets to the enemy, then go have that meal he was planning on, or a drink. In other words, not only does the AI of the Heroes need to be able to change on the fly, but each hero also needs a Line Of Sight mechanic. Of course, the LOS mechanic would mean that unless a hero has direct access to the King or the king's advisor, they would have to check at a "adventurer's guild" type building to see if there is an Attack Bounty out across the map where the hero cant see.
As i read in a post, heroes being able to "evolve" would be an amazing new mechanic, especially when you bring ideas from other games into it. For example, a Warrior with high intelligence could evolve into a Spellsword with access to basic magics of various other groups, like Fireblast and a defensive spell. A Ranger who specializes in poisons, because he spent too much time in the Thieves's building, would become a Poison Archer. That was a bad example. However, if an evolving mechanic could be added, the strongest evolutions would have to be confirmed by the King(player). Say a Warrior managed to barely kill a dragon on his own, he could get to become either a Dragon Slayer, or a Champion, both of which would need to be acknowledged by the King. Other examples could be if a party went into a Goblin Fortress, but only 1 hero survived, they would gain the trait or Secondary/Sub class of "Survivor", and they're class would read as "Paladin(Survivor)".
Just plain having more options for heroes would be amazing. Examples could be, for non-religous heroes, from a Jousting Arena a Cavalier on horseback could be hired, or a Gladiator from a Colliseum type building where other heroes can go for combat training and betting on matches.
A way to bring back "Kingdom Decoration" type buildings would be that you could make "Kingdom Requests" at the "adventurer's guild" type building i mentioned earlier. By making a request to your heroes, they could go on a quest that takes them out of the map to collect relics. When the hero, or party, gets back, you would then be able to build a Monument to the achievement.
As was mentioned before, monsters need variety. A hero would get bored of the hero's life if all he is doing is slaughtering the same goblin over and over and over again. From what i remember about Maj1, the enemies with the biggest variety were the Goblins and Ratmen, which both had an almost kingdom-like variety of troops, and buildings when speaking of goblins. Dragons had what, 3 varieties and 1 was a boss? Kinda sad for them. Of course, if undead are all a single species, then they are comparable to Ratmen and Goblins.
The biggest change, to me, would be if you could start at, not a lvl.1 castle, nor a Outpost, but rather, the castle starting out as a simple Mayor's House, and from there leveling the "castle" up.
For connecting different missions together with the map idea from Maj1, you could make each "territory" persistant until you replay that map. Say you play a mission from Maj1's map, beat it, then move onto a mission next to the previous one. If you start to have a spot of trouble in the mission, you could call for aid from the settlement of the previous mission. The "Aid" sent could be high level heroes from the previous mission who have a timer before heading back, or supplies in the form of gold.
Speaking of missions, the unlocking mechanic from Maj1 was actually interesting. If they could rework that, bringing back the Map would be easy. Say you beat 2 missions and unlock the next, the new mission's intro would point out how the other mission's brought you to this one, making it into an actual story, rather then random stories across the map.