To garner DoFs you do not need to exchange embassies, open borders or trade with them. Embassies is a "small bonus", and "trading recently" only gives bonus if the trade was heavily in the AI's favor, or in other words, giving them stuff.
You biggest bonuses to DoFs are "friends with same target", "denouncing same target" and "war with same target". You can watch the diplo tabs and see who's denouncing/friends/denounced/at war with with whom.
You can pick a side "early" (though it doesn't matter much til education unless you really need their help in multiple DoWs) or you can wait awhile til "sides" inevitably form. At this point you can "hop on the bandwagon", denouncing their targets and accepting their offers for mutual DoW.
Generally at some point the AIs that used to be enemies can/will have your better interests in mind. It's wholly possible to repair bad faction over time with constructive use of the above info in "retrograde", as long as you haven't taken their capitol, broken promises, stolen their land with great general, or earned huge (bright red) marks for city state competition or attacking their protected city states. These actions, even if you make friends later, are severe detriment to diplomacy.
These can be eventually fixed, over time or finagling: having been at war, dow on friends, friends with enemy, covet lands, warmonger or any denounce activity.
edit: I forgot to add the industrial age policies. You can lump sharing those in paragraph 2 above. Sharing religion is a bonus modifier, but I've not found it particularly leads to friendships if the rest is ignored.