On the turn you first come into contact with a civ there is protocol to follow:

• Say "It's an honour to meet you" and accept invitation or to exchange info. This will reveal one of their cities.
  
• Spend $$ for a delegate or embassy.
  
• Make an open borders agreement, if you have Early Empire.

(Similarly after war, on the turn you make peace with a civ, the AI will possibly acquiesce to an open border agreement. You may have to sweeten the deal with a little gold/GPT or a strategic resource).

It is a common misconception that waging war will be bad for diplomacy. In the long run, securing your capital and lands by waging early war with your nearest neighbours can in fact lead to a long lasting peace, for the long game. Secure borders will help deter the AI from warring with you.

You can even eliminate civs completely in early game warmongering and still build an alliance with civs later.

Denouncing a civ will earn a permanent diplomatic penalty, so only denounce a civ if you plan on eliminating them or need to declare a Casus Beli.

The enemy of my enemy is my friend

Joint Wars are a great way to befriend civs early game. It will give you a diplomatic buff with that civ at the expense of others though.

On the plus side, you may not need to denounce a civ first, in order to declare a joint formal war or joint war with a casus belli.

When you liberate a city belonging to a a civ or a city-state, you negate accrued warmonger penalties.

Bringing a civ back to life will grant you 300 diplomatic favour. +100 otherwise.

A strong, upgraded, elite military will deter the AI from warring with you. If and when they do you'll be able to better terms of a peace agreement.

Make a trade route with a civ for a diplomatic boost.

Trade excess luxuries and strategics.

When a civ proposes a deal, if it isn't beneficial to you be sure to suggest instead an excess strategic resource (E.g: iron) or even petty gold to avoid refusing their offer of trade.

Each leader has agendas.

For Mvemba a Mzinga (Kongo): convert one of his cities to your religion (assuming you found a religion). Harald Hadrada (Norway) likes you to have a strong navy.

Some are easier than others, agendas can be a simple way to befriend a civ.

If you want to befriend a certain civ, having the same government helps.

Generally founding a religion and/or pursuing a religious victory is likely going to be bad for diplomacy. (Apart from with the Kongolese and perhaps India).

Civs who've founded religions don't like you converting their cities. It gives them a casus belli for declaring a Holy War. Not even do they like your apostles and missionaries waging passive religious warfare with them. That also has negative diplomatic repurcussions.

Conversely not founding a religion can benefit relations. Arabia and Spain are two civs you can befriend if they convert you.

Send spies on Listening Post missions to boost your diplomatic standing with civs.

Stealing tech, art, gold or sabotage will be bad for diplomacy if your spies are caught.

Originally posted by Baron Vladimir Harkonnen from Dune:

"He who controls the spice, controls the universe!"

If you are able to monopolise (i.e possess in your borders all copies of a luxury, the AI will have to trade you for them. (Most noticeable on a map like 6 Armed Snowflake).

With the latest updates the diplomatic penalties for warmongering has increased. To minimize this be sure to use casus belli to declare war in the later eras.

Protectionist & Liberation Wars are best cos they carry zero warmonger penalties. Holy Wars and Colonial Wars next, for warring against civs who've converted your cities to another religion and for declaring against wayward civs.

Though capturing a settler is better than having a foreign city, even if it is traded/ceded to you. So you may have to compromise.

If you want to maintain good relations with a civ don't excavate artefacts from their lands. It incurs a diplomatic penalty.

Once you see the green smily status on a civ you may ask to Declare Friendship. Then with the Civil Service civic you'll be able to make an alliance.