Playing on Immortal, and at first I assumed that this was to be expected, but now I realise there's no counterplay to it. I don't know what handicaps they get, but I think it may go beyond reason. There is NO way to compete against their missionaries & diplomats. You can dedicate a city to being a diplomat producer, but the AI will get 3 diplomats out in the time it took to get 1 out for you.
I messed with difficultymod.xml to make it better for myself, but I thought I'd put these thoughts out here to see if others agree or not.
So the trick, once you get to Emperor (and especially Immortal play), you have to completely rethink your diplomatic strategy:
1) Early game is about quests as normal. You secure quest combined with the occasional emissary to lock up CS.
2) All GDs should be used for embassies, with very rare exception. These are going to be critical extra votes for you.
3) Into the early stages of envoy, you can still secure key alliances. Some envoys combined with your first spy and some good quest use, and you can lock up some nice alliances.
4) Now once you get into Renaissance things start to go downhill. The AI "wakes up" to its amazing production potential, and starts making GDs and diplo units like its going out style (spoiler: it never goes out of style).
At this point in the game, you have to come to a key realization for your future success.... Diplo units no longer exist to secure alliances. That part of the game is past. Your goal going forward is to use Sphere of Influences to secure alliances, it is the only reasonable way to do it. Meanwhile you begin using diplo units on "Operation Total Friendship". Your goal now is to secure friendships with every CS you can. You will still get decent bonuses from friendship, still get nice bonuses from chanceries and wire services.... but at a tiny fraction of the cost as trying to beat AIs to alliances (and with much less diplomatic penalty to boot).
It doesn't actually take a lot of effort to get to all of the friendships, and then from then on you do the following:
1) Ask for a sphere every time a WC comes up, unless their is a more important proposal you need.
2) Focus on GDs early in the game (often my "free GP" go to them as well in the early game). Make embassies for as long as you can, this will actually be a solid portion of your voting block. Once the embassies are gone, say goodbye to GDs. If you get them, feel free to soften up a CS...but again your not going to gain much ground on the AI here.
3) Keep a few diplo units handy for friendship maintenance (mainly to counter AI GDs that will strip your friendships). Send a unit whenever a GD hits a CS to resecure the friendship.
With this strat, diplomacy is manageable and will still reap you some good bonuses. Anything other than this and you are just fighting up a mountain in the rain with a 10 ton weight on your back, so don't do it!