I was happy that negotiation was at least touched on in
Skyrim, but I think that there's a lot more that could be done with it. Getting rival generals or rulers to switch sides through negotiation, or their cities to switch sides after getting them out of the way through assassination, would be very interesting in my opinion. And I think negotiation should have some more serious results than just changing the name of the ruler in a certain city, though I'm not sure exactly what more they could do. And what about the guilds in these territories? Summoning the Dark Brotherhood (or local variant) would be interesting, though I'm not as well versed with the Brotherhood's rules enough to say whether or not it would be within their parameters to kill every enemy general or ruler you don't want in your way. Getting mercenaries from the Fighters Guild (or whatever equivalent the setting demands) could be a minor quest for a faction newbie; the same could be said for getting battlemages from the Mages Guild.
Also, it'd be interesting if the enemy was reacting to what you were doing--if you took City X, they might attack City Y, or ask for a ceasefire in order to negotiate something, etc. I think there are plenty of directions they could take with this, as long as they wanted to focus on it in the future.