Here's a list of all the leaders in the game, with comments for our expected relations with them.
First of all, it seems obvious to me that we must adopt Free Religion at some point, the bonuses from shared religion with a few civs simply cannot outweigh the massive negatives we will get from everyone else. So I've disregarded all shared/heathen religion bonuses/demerits from my thoughts.
My tentative thought is to aim for a win in ~120 turns from now. If we meet the other continent between 30 and 50 turns from now, that means 70-90 turns to befriend them.
Alexander
I've already told you that I consider Alex a lost cause. Probably the biggest reason for this is that he is the worst enemy of too many others, so any effort we make to befriend him will hurt our relations with those others.
If we really tried, and got him to the point where we could sign an OB with him, we could perhaps expect to get the following bonuses: -1 base (that's iBaseAttitude - 1 (for Deity)), +1 years of peace, +2 OB, +4 for Fair Trade for a total of +6.
This assumes that we have a better rank than him, and that we are not both on the bottom half (seems like we're going to stay in the upper tiers for some time to come). +6 is not +8, and seems hard to find those final +2, not to mention this doesn't take any negatives like worst enemy trade into account. He would need 10 techs traded to him in order to give us a +1 shared tech bonus. There's bonus resource trade of course, but it still seems very hard to me.
Also, I'm willing to bet that Washington is planning a war against him. We would perhaps be better off joining that war instead of trying to please Alex.
Summary: Lost cause
Asoka
The modifiers we know and can count on are: +0 base, +1 peace, +2 OB, +2 bonus trade.
That's +5 before any Fair Trade bonuses are counted. He'd need 20 techs for a +1 shared tech so that's not really feasible. But getting to +3 Fair Trade doesn't seem impossible or even improbable. Asoka is the leader in rank (of those we see anyway), he likes those of higher rank a lot but it seems unlikely we would overtake him. No negatives for those of lower rank at least. We might go for US late in the game, so perhaps a +1 wise civic bonus or two.
Summary: Easy
Catherine
We don't know if she's in the game or not, could be Peter.
Base attitude is 0. She would sign OB already at Annoyed, so getting +2 OB out of her should be easy. +1 peace of course, and +4 Fair Trade perhaps (easier to get fair trade modifiers with those we haven't met yet). That's +7, not quite enough. We likely won't go for HR (and she will probably be out of it by then). She might make a good target for some bonus resources for an extra +1. She needs 7 techs in order to give a +1 shared tech modifier. She gets negatives towards those of worse ranks and no bonuses towards those of higher rank.
Summary: Potential
Cyrus
Base is 0. Cyrus would also sign OB at Annoyed so +2 OB should be easy. +1 peace as well. Also, Cyrus has the advantage of having a good favored civic, Representation, though with a cap at +3. If we stay in Representation to the end, and he does too, that's +6 before Fair Trade is counted. He could potentially give a (hidden) +1 for us being higher rank than him, but it would require that we are 10 ranks above.
Summary: Easy
Elizabeth
Our friend and neighbor. She loves Free Religion so depending on how early we switch, it should be easy to get her above the limit. More specifically, her base is 0, we get +1 peace and +2 OB, potentially +2 bonus trade, and likely +5 civic, for a total of +10 before fair trade. She doesn't care about rank at all. We probably don't need to supply her with resources, we'll get her there anyway.
Summary: Given
Frederick
The big problem here is of course his rivalry with HC. We need to balance on the knife's edge. What we know is that we'll have +1 peace, +2 OB and most likely +2 bonus trade as well. Base is 0, and he cares about rank as much as Cyrus, i.e. we need to be 10 ranks higher to get a bonus, not likely. Favors US which we may or may not want to switch to. So +5 before Fair Trade bonuses, and also before rival trade demerits for HC. The -1 "you refused to help us" will wear off before the end. Requires 7 techs for a +1 shared tech bonus.
Summary: Potential
Hatshepsut
Hatty signs OBs at Annoyed so same thing goes for her as for the others. Base is 0, +1 peace, +2 OB for a total of +3 before Fair Trade. Favors HR which we don't want. Dislikes those of lower rank, cares for those of higher rank as much as Cyrus, i.e. 10 difference needed. Needs 10 techs for a +1 shared tech. All in all pretty hard to please.
Summary: Difficult
Huayna Capac
Our buddy who is warring with Frederick, which gives us problems. HC's base attitude is -1 so a slight uphill slope from the start. +1 peace, +2 OB puts us at +2 total. Even if we got him to +4 Fair Trade, and with no rival trade demerits for trading with Frederick, that's still only +6. Cares little for rank, and favors HR. This guy won't vote for us without some other reason.
Summary: Difficult
Isabella
This is one nasty girl. She starts at base -2, and is generally unlikely to listen to anything we say. If we can get her to +4 fair trade, and +2 OB and +1 peace, that's still only +5 total. Where do we find the remaining +3 needed? She only really likes those of her own religion, and we won't be one of those. She favors Police State which we definitely won't choose. She needs 20 techs for a +1 shared tech, not feasible even if she's way behind.
Also, Izzy is playing OCC, and a rather low-pop one at that. That makes her vote worth less than half of that of the others.
Summary: Lost cause
Julius Caesar
Another friend of Representation. Starts at -1 base though, but with +1 peace, +2 OB and +4 civic that's +6 before Fair Trade is counted. Needs 10 techs for a +1 shared techs, no rank bonus.
Summary: Easy
Kublai Khan
The biggest problem with KK is that he likes Alex and dislikes Washington. He starts at -1, and we don't have an OB with him. He's rather backwards though, so it's not impossible that we could gift him a few techs to get his Fair Trade up, and get an OB for that. We don't know if he's the worst enemy of Lizzy though (or do we?). He needs 7 techs for a +1 shared tech. And perhaps most interesting, he'd give a (hidden) +1 rank difference modifier if we are 7 ranks ahead of him, +2 if we are 13 ahead. If we count +1 peace, +2 OB, +4 Fair Trade, +1 shared tech, +1 rank, that's +9. So unless this guy means to make trouble elsewhere, I don't see him as a lost cause. Though if we attack Alex, we will get a -1 with KK for that. And trading with Washington will keep racking up rival trade demerits.
Summary: Difficult
Louis XIV
We don't know if he's in the game, could be (hope for) Napoleon. King Louis starts at -1, dislikes those of worse rank, favors HR. He would sign OB at Cautious. -1 base, +1 peace and +2 OB means +2 total before Fair Trade. Needs 10 techs for a +1 shared tech. Hard to see how we would get him to the +8 needed.
Summary: Difficult
Mansa Musa
Everybody's best friend, potentially only rivalled in that regard by Gandhi who isn't in this game. Mansa starts at base 0, really likes those of higher rank (+1 if 5 higher, +2 if 10 higher, +3 if 15 higher), would sign OB at Annoyed, and only needs 5 techs for a +1 shared tech bonus, 10 techs for +2. He also favors Free Market, a civic we may well want to adopt later in the game. At +1 peace, +2 OB, +1 shared tech, +1 rank, at least +1 Free Market, that's at least +6 before Fair Trade.
Summary: Given
Montezuma
I guess it's no surprise that this guy won't be easy. He starts at -2, favors Police State, hates those of worse rank and doesn't care at all about those with higher. Needs 7 techs for a +1 shared tech bonus. Signs OB at Cautious. With -2 base, +1 peace, +2 OB and +1 shared tech, that's +2 before Fair Trade. I don't see how we could recover from that.
Summary: Lost cause
Napoleon
We don't know if he's in the game or not, but very much hope that he is, he's much better for us than Louis. He really likes Representation and will go up to +6 for it. He starts at -2 though, signs OB at Cautious. With base -2, +1 peace, +2 OB, +6 civic, that's +7 before Fair Trade. Will need 10 techs for a +1 shared tech bonus. Doesn't bother much about rank either way.
Summary: Easy
Peter
We don't know if he's in the game, could be Catherine, we don't particularly care. Peter starts at -1, signs OB at Cautious. He favors Police State. His main redeeming factor, if you could call it that, is that he will only need 5 techs for a +1 shared tech bonus, 10 techs for +2, like Mansa. He dislikes those of worse rank and likes those of higher like Cyrus, i.e. +1 (hidden) for 10 difference in rank. With -1 base, +1 peace, +2 OB, +1 shared tech, that's +3 before Fair Trade.
Summary: Potential
Saladin
Starts at -1 base, favors Theocracy. He likes those of better rank as much as Cyrus (+1 if 10 difference), and needs 10 techs for a +1 shared techs modifier. With -1 base, +1 peace and +2 OB that's only +2 before Fair Trade.
Summary: Difficult
Tokugawa
Starts at -2, favors Mercantilism (very unlikely). He will be very difficult to please, he would need 20 techs for a +1 shared tech, doesn't care about rank much. If we can get him to Pleased and keep him there, we might get the +2 for an OB. I'd rate that as unlikely though. I just don't see how we could possibly get him to vote for us. Like Izzy he has only one town, and a small one at that.
Summary: Lost cause
Washington
Starts at -1 base, and we also have a -1 close borders. He favors US, doesn't care about rank, requires 10 techs for a +1 shared tech bonus. That latter doesn't seem unlikely though, considering we've already traded him a few. At -1 base, -1 close borders, +1 peace, +2 OB, +2 bonus trade and +1 tech means +4 before Fair Trade.
Summary: Easy
Total summary:
- Elizabeth and Mansa will vote for us without a doubt, as long as we can avoid wars with them.
- Asoka, Cyrus, Caesar, Napoleon and Washington will vote for us with litte effort from our side.
- Catherine/Peter and Frederick will likely vote for us if we make the effort.
- Hatty, HC, Louis and Saladin could vote for us but will require some special effort.
- Alex, Izzy, Monty and Toku are lost causes.
The special measures we can also take that I haven't considered above are Defensive Pacts and Shared Wars, as well as quite a few Bonus Resources to some leaders.
- Defensive pacts give +1 per 12 turns up to +2 after 24. We can only have so many though before we start incurring negatives with everyone else. As long as at least 15 out of 18 civs are still alive, we can have 3. If 11-14 are alive we can have 2, 7-10 and we can have 1.
- Shared wars give a lot of bonuses, but only while the war lasts. And declaring war on someone incurs penalties with that civ's friends (pleased with or better).
- We will want to count on the Bonus Resource trades, to make sure that we send them to the proper places at the proper times. It's 50 resource-turns for a +1, 100 for a +2.
Then there's also the big issue regarding who would be our opponent. We would love for it to be someone on the other side, someone who has conquered some neighbor and grown powerful from that. Someone who is not so easy-going and likable, like Saladin or Louis or Monty. On our home continent, HC would be the best bet, if he can conquer some of the German lands...