There should be UN Resolutions. One of them could be something about the customary law principle of fishing vessels in wartime being protected from destruction (if signed onto, any violation of it should result in lower diplo ratings). Other UN Resolutions like Stopping a War and so on would help make diplomacy more nuanced--not helping a friend of yours by vetoing a resolution terrible to him should result in your friend disapproving of you more, etc.
There need to be more ways to get AI to like you, i.e. trade, and mutual military cooperation. Also, that whole "you built wonders we liked" ought to be removed, it's stupid. Especially since the human player shouldn't be expected to constantly map scroll to see what wonders the AI is building in the shadowy dark.
And yes, allow for religions from AI to peacefully coexist--allow cities to adopt multiple faiths, but allow only one state religion per player, as in Civ IV. But only the founder of a religion should be able to enhance that religion (incentivizing players to stick with religions they founded, but switching over to religions AI players found may be preferable for diplomatic bonuses, maybe).
INTERNATIONAL TRADE ROUTES PLEASE.
And in line with the "we're part of a bigger world than just ourselves" theme, allow map trading with Optics or Astronomy. Maps from the AI should be expensive, but not impossible to get.
Allow AI players to Demand things from you aggressively, and allow them to gloat when they beat you in war and get you to surrender.