I don't think that a linear storyline* would be good for M&B. Though, more depth to the faction quests, instead, would be much more interesting. For example, the player would be given different (harder?) quests once he achieves higher ranks in the faction royality. These would actually have consequences in-game. Quests for town capturing or noblemen killed, for example. It would add so much to the game if the NPCs (all of them, that includes Borcha, Marnid, the kings and the counts names) would be all randomly generated at the start of a game. There could be quests for assassinating/capturing counts or whoever, and they'd be replaced by another by their faction.
* If you examine the units and conversations files carefully, it seems that the developers had a storyline in mind that involved some girl, necromancers, knights and the like that for some reason was left out of the native mod.