I think that simplifying the whole haggling mechanism is the start of the solution, not the crux of it. That is the least important decision you'll ever make and should be treated as such, instead of a part of the game that will consume 2 minutes of your time in extreme circumstances.
With that, it's just as simple as making diplomacy mean something. I have a few ideas (that don't necessarily depend on one another).
1. More resources with a greater variety of resources
Make it nearly impossible to have every possible resource within your borders. That way you're FORCED to trade with someone else.
2. Discrete supply of resources
Instead of letting one spot of oil power your entire armada of battleships with a probability of that oil disappearing, there should be a discrete supply of each resource that can be measured, like gold. This way, someone who has a resource has to ration it, and someone who trades for it can be held at the mercy of who holds the supply.
This should probably be combined with #1: greater variety of resources, so no one nation holds every other nation at mercy for everything.
3. Multilateral trade
Why not? Especially if it's an innovation towards the end of the middle ages, it lets you naturally scale up to a "United Nations" instead of making it this wonder that sudddenly turns the world into something to be ruled by one person.
4. Discrete trade routes
Discussed in another thread, I think discrete trade routes would make transportation and overall security more important. A volatile Near East throughout the middle ages prevented much contact between Europe and the Far East. And when Portugal finally got a ship over there, it was a big ****ing deal.
Being Italy in the middle ages was really important because it was the trade center of Europe for a while. They had easy access to many different trading partners via the Mediterranean. They got pretty rich in this time partially because people would need to run their trade routes through Italy's territory. This is particularly important with multilateralism, as seen in #3 above.
And being Switzerland now is really important because they're NEUTRAL -- the world trusts them, and there is nobody they don't trade with. If you make war with a lot of people, either you're hated, or not trusted -- do you really want to get into a long term trade agreement with someone who very well might attack you, or who very well might be attacked and unable to get their promise to you?
4. Military trading
Leasing units, training units, providing weapons to units who figure out their own training. However it happens, it should happen. And it should be able to be done discretely, with nobody knowing -- unless, of course, they're using powerful intelligence and espionage.
5. Greater emphasis on intelligence
Yep. There should be a greater variety and different kinds of information you can tap into on your allies and enemies. Knowing what they're building is one thing, but tapping their diplomacy screen is valuable (along with the ability to uncover taps).
Being able to instigate propaganda not to flip a city, but persuade their audience is valuable. I guess this would tie into a greater variety in domestic problems -- but I think you should be able to instigate these problems. War weariness is an obvious example. The smartest kind of "information warfare" is to do something so savage and brutal to the opponent, that no matter how winnable the war seems, it seems not worth while. Or, on the flip side, to publicize and advertise the civilian casualties within your borders to raise sympathies and make the other guy look like a jerk.
Of course, I'd like to see this go deeper than war weariness, but then I'd be biting off a much larger chunk of the game than I care to discuss.
6. Greater benefits from international trade
I think this is severely worth doing. Having silks within your own borders offers some small gold benefits. But moving it across borders, so to speak, should be worth 10 times as much. Especially when combined with #1 (greater variety in resources) you could see people trading so many different commodies in a mutually beneficial deal. "Yeah, having 10 salmon is great. But having 5 salmon and 5 cod is even better!" Not that the user would need to keep track of 50-100 different resources, but only that the user would have to understand the benefits of "fish" and that salmon and cod are two different types.
This way it becomes more profitable to interact than to isolate. In fact, it makes interacting a necessary evil in order to get ahead.
7. Greater penalties from jerk moves
Sure there's enough to be lost when we talk about the ideas above. It's obvious that foregoing trade and allies makes you miss out on key benefits. And certainly a trade embargo against you for being a jerk would seriously hurt you.
But breaking a Right of Passage agreement shouldn't just hurt you in the eyes of the world. It should hurt you in the eyes of your citizens. Not to say that they'd start hating their nation, quite the contrary, they might love you for it. But the citizens, recognizing that sneaking up on someone and backstabbing them is an intelligent and appropriate way to settle conflicts, begin doing that to one another. Your nation becomes more corrupt, more chaotic.
8. Reward for liberating allies
Conquering and keeping territory should always be profitable. But right now, there is no motivation to do the noble thing and help somebody out. Even an alliance is insufficient. I've had alliances with computer players that I basically say "enh, let them fight it themselves", if not an excuse to loot and keep territory for myself. I'm suggesting an alternate victory type. You guys have heard this before: glory victory, where returning a territory to an ally earns you points. And if you acquire enough of these "moral points" you win this Churchill style victory.
If there's a reward for playing like Hitler, then there must be a reward for playing like Churchill. In fact, that's gonna be my new motto.
9. Slave States, Puppet Regimes, and Colonies
Combine this with discussions I've had on AI, where some Civs don't play aggressively but play to enhance the simulation aspects of the game.
http://forums.civfanatics.com/showthread.php?t=101196
A few superpowers, you and the AI, compete not only by conquering territory, but by having favorable regimes towards you. Having a Colony that is subservient to you and provides you with a variety of resources -- this was an important fact in the pre-industrial era, right up until the modern era. Puppet regimes are a fact of the modern era. This kind of complexity makes the late game very compelling.
10. Civil War at medium levels
I think Civil War should be a fact at medium levels. Combine this with greater emphasis on intelligence (#5) and you now have an avenue for people to mess things up even in the peaceful world -- let's instigate a civil war! Not only that, but conquering certain nations would make your empire more divided, thus making it harder to be expansionistic and forcing you to consider other ways to extend your dominance. Or think of ways to do it in a slow and stable way.
11. More "Historical Facts" at Higher Levels
I hate to be an advocate of limitations, and I try to avoid doing it. But I think this would make the game much more interesting. The modern game, as it stands now, is tired. It's worse than the early game because the territory is all settled, so it's basically the same thing over and over with new units.
Imagine that in the industrial age, you can no longer conquer. Instead, you must colonize and occupy. The end result is the same -- you can inch closer to a domination victory. But the catch is that you have less control over the colony, and eventually the colony will overthrow you (by the modern age).
The modern age, too, could be different, forcing more strategy instead of blind war. The USA can't just Carpet Bomb Iraq -- and as much as some people think they should, the world has moved towards the Geneva convention. This forces people into diplomacy and greater intricacy in war -- instead of the easy victory provided by rolling over Iraq with Tanks.
Again, this would happen at higher difficulty levels.
Combine this with risks of civil war, and you have a really compelling second half of the game for the first time. All the land is taken, yes, but now it shifts from expansion to imperialism to neo-imperialism. The game changes, and so do the strategies.
12. Nuclear Deturrants at the Highest Levels
Imagine that no more than 5 nuclear weapons are allowed to go off, or the game ends in a draw. Now THAT'S challenge. That's the kind of fear that paralyzes the world even today, but especially during the cold war. USA and Russia never would have attacked each other -- if they did, it would have been the end of the world. USA launches a Nuke, USSR launches a Nuke, anyone else who has a Nuke launches a Nuke, and before too long the world is essentially a wasteland. The balance of power between USA and USSR was maintained for this reason -- forcing more tricky ways to rally for power. Particularly covert regime changes in Latin America (see 4 for military trading, and 9 for puppet regimes).
Combine this with some of the thoughts on Type B Civs, that play to add a simulation type elements, and all of the sudden the most powerful AI and you are trying to broker peace to make sure nobody launches a Nuke (and keep Nukes out of the hands of horrible regimes).
Conclusion
I think I went a little crazy here. But I just wanted to keep the discussion rolling and put people on the imaginative track, also forcing them to recognize just how important diplomacy can be in making the game better. Diplomacy is perhaps the most interesting thing going on in the world today -- and yet Civ tries to repeat the same old wars right up until 2050.
The most contraversial suggestions are there at the very end. But they are, once again, only there to stimulate discussion.
This is one of few times I'm too lazy to clean up and tighten the ideas. Right now is the brainstorm. Maybe one other later time, I'll tighten this up into a nice little proposal.