Possible rule additions:
Free Passage: an army may pass through another player's territory without attempting to conquer it, but only if both players agree. Said army can defend that territory for the host player in an attack, and can attempt to seize the territory as a free action on its owner's turn or during any battle for that territory.(not a movement, so another army can still move)
Adds diplomatic options, including the possibility of alliances to attack or defend a territory. Have fun deciding who gets to rule a territory you allied to take though. Backstabbing is also an option, so watch out.
Vassalage: when a player is eliminated, the player who defeated them can choose to leave the last army alive. The defeated player cannot attack them for 5 rounds, and their armies count towards the territory limit of their master. They cannot recruit their own armies, but their master can choose to recruit for them. They still move on their own turn. Territories they capture are given to the player they serve. After 5 rounds, they can at any time choose to start a rebellion, at which point they are their own player again, and can capture territory for themselves, including ones currently occupied by their troops (like those owned by their former master)
Making someone your vassal gives you an extra general to work with, but comes with the inevitable betrayal when said vassal wants to get back in the game later. Just be careful how much power you want to let them have.