charon2112
King
Quite frankly ... Civ V. As much hate as the AI gets, and despite issues with implementation (among them the "trade anything for gold" issue) the diplomacy system Civ V uses is rather innovative and departs from the trade screen of previous Civs and most strategy games in favour of diplomatic relations that are based largely on tripartite relations. It makes it actually feel as though you're interacting with other players with their own alliances, enemies and interests.
The downside is, it's a lot more complex than a typical modifier-based system, and AIs are notoriously weak at handling those. Which is probably why Civ V AI failings in diplomacy get so much flak. But it's certainly the best diplomacy system I'm familiar with.
As for other games, Distant Worlds has quite involved diplomacy, but mostly in its more detailed implementation of economics (trade isn't automatically halted by empires at war; there's a sanction system that allows you to control trade restrictions with hostile powers) . However, the fact that you can have multiracial populations on planets, and immigration and emigration from other empires (as well as ways to set immigration controls), adds a level of detail to diplomatic relations: your reputation with other empires is affected by how you treat their conspecifics.
The Total War games have family trees and a diplomatic marriage system, as well as the ability to exchange hostages (underage members of your lineage) in exchange for favours.
However, TW diplomacy is somewhat rudimentary - the only real way to influence relations is to initiate trade agreements, which are binary and automated (you don't get to set what resources are traded). There aren't many diplomatic agreements you can make (basically, military access or alliance), and vassalage while nice in theory appears to be largely pointless in practice (only a very weak state will agree to be a vassal, by which point you might as well conquer them anyway, particularly since you'll do a better job of protecting the province than the AI. Civ IV's vassalage system had the same issue; I'm not aware of a game that's resolved it). There are also flaws in both AI and implementation (for instance, if another power breaks off an agreement with you rather than vice versa, you still take the diplomatic penalty - with them and with other powers - for not honouring an agreement. Civ V used to do this before patching, and that caused a lot of complaints too). There is a religion system that has significant effects on diplomacy, and with the most recent DLC for Shogun 2 there are clans with all three of the game's religions to choose from, however managing this is essentially outside the player's control.
The AI is programmed with set religions and will never change, even if you manage to convert 100% of their populace to a different religion, and so you have no way of influencing diplomacy through religion other than by changing your own.
And because of the way TW games work, mostly you want diplomacy as a means of keeping certain powers in line while you beat up everyone else, not as a way of forming meaningful long-term relationships. As such the diplo system inherently lacks character - it feels like a game mechanic rather than a way of usefully interacting with other powers. On the plus side, it generally does a good job of representing tripartite and other multipartite relations - you do need to track who's allied with who carefully, as allies of your enemies will be very inclined to declare war on you in turn.
As of the G&K expansion, I've been pretty impressed with Civ V diplomacy also.