Sandbox Story-Arc Quests.
Each Sovereign should have a bi-directional plot line to follow (if the player chooses to) in the sandbox mode BEFORE the Quest for RPG victory can be started.
What I mean by "bi-directional" is that each sovereign has their 'natural tendacy' and their opposition to that tendacy. As the player, you should be given the choice through the story arc quests to follow a good path or an evil path.
IMO, including this approach would help make RPG more balanced compared to the other avenues of victory. Granted, it still may be the easiest to achieve....but at least it's more time consuming.
I should probably comment, that since Frogboy has already mentioned that he wants to keep 'campaigns' in the campaigns; I would like to rebuttal again and note that Sandbox Story-Arcs don't HAVE to be campaigns. They can be loosely followed series of quests that your sovereign can follow if you decide to do so. The story of the campaign was EXCELLANT. I really enjoyed it. The concept of the 'campaign mode' however, I hate to admit (and it is only my opinion) sucked.
Lastly, on a side note, if you are attempting to persue the Spell of Mastery victory.....eventually everyone should be turning against you. No one should just be LETTING you win.