It's hard to please everyone and you probably can't be friends with all your rivals. Because, then you wouldn't be able to do trade with anyone in fear of provoking their enemies. And if you wanna please all, you need to give into their demands, because then you're safe from harm for 10 turns, at least...
Diplomacy is hardly my own strong suit but I would suggest that you have a plan for your relations. Choose who your friends and allies will be, nurture those relationships, even if it means short term penalties or making others not like you. Its not a popularity contest, after all.
Religion can be a key factor, as some leaders are quite the zealots. Isabella and Saladin come to mind...

If you wanna be buddies with them you need to have their religion, period. Another approach to please the most amount of rivals could be not to have a state religion - at all. You'd loose the benefits of most of the religious civics, though, as well as the positive attitudes from the leaders you wanna bond with. So you should choose religions wisely and perhaps join the Apostolic Palace club to make friends.
Also, take note of whom likes and dislikes whom, and pretty much pick sides. You don't need the potential trade routes that comes from Open Borders with everyone, after all, but make sure to have civil relations with a few far away, wealthy and advanced Civs to get those intercontinental trade routes.
Lastly, some leaders are simply unreliable and will never be your friends. Forget about getting to third base (or any base for that matter) with Montezuma or Genghis Khan, for example. Those bastards are your default enemies and you should probably ally with their worst enemies... And thats anyone else. Others may just back-stab you or take advantage of your good nature. I'm looking at you Catherine!
I believe there is some kind of guide to all the leaders and how to deal with them. That or you could just open the CIV4LeaderHeadInfos.xml file and look at their individual settings. There will be skeletons in the closets.