According to what I tried.
I finished about 19 games, and started perhaps 50, using all available civilizations ... Which means that I was quickly crushed (or without ANY hope of surviving) 60% of the time!!! and I am optimistic...
I play always at Monarch level.
Of course, this ranking is according to my feelings and game style (I am more a builder than a warlord), etc... and can be totally different for someone else!!!!
%UHV : % for having the game offering you a decent chance for winning a Unique Historical Victory
% Classic: chance for reaching a regular victory (ex.: space, points...) in RFC, NOT in Beyond The Sword, and IF you do not go first for a UHV (most UHV targets are NOT compatible with other victory types)
%UHV - %CLASSIC - CIVILIZATION - OBS.
20 30 Carthage Surrounded by sharks - must expand too quickly
Carthage is remarkably easy so long as you keep your eye on the prize. You don't need more than 5 cities, and these should be Qart-Hardesh (sp?), Athenai, Jerusalem (however its spelled at the time), Barca, and next to the 2 dye north of Jerusalem. Your first settler build Q-H, your second should go with your military to crush the coastal cities in the holy land - you'll raze sur and rebuild on the hill north of it (it'll be too small to take). You'll need to take or raze Babylon, so get some catapults (athens is a good building city). Otherwise focus on economy and hire mercenaries for your dirty work - you get them cheap, and dead mercenaries require no money. Athens should also build a settler for Barca. That's 2/3 UHV goals, and once you've dealt with Babylon you can tech like a bandit for Optics. I finished around 860AD on my first try.
25 35 Khmer Jungle late development (biology)
Most of that jungle is Calendar resources - developing them will clear the jungle pre-biology. So don't sweat the small stuff. You'll need to Caste System 3 GAs to get the culture, but you have plenty of time. (If you can get music first you can have all 3 by 1300 easily, 150 years early, even if you pop a non-GA first. In fact, i popped a GE first, and used him to go into a golden age, which helped immensely with generating 3 GAs - one from each of 3 cities). I founded Angkor, Singapur, and Hriji...something or other (north of where Hanoi would be) and captured Pagan and the southernmost "chinese" city (its either Guangzhou or Huangzhou i think) - they were all easily 11+ by 1450, despite a plague in the meantime.
The only reason i haven't actually completed this one is because i got bored with the 30% buddhism part. (And distracted by that stupid sacred sea quest - which i now think is impossible in RFC since you need biology to chop jungle so you can build on 85% of those islands).
30 30 Persia Must go at war too early - unstable
... This one was pretty easy, and "too early" is a big stretch. Heck, i screwed up and tried to attack greece by land (letting them move all those frickin phalanxes into athenai) instead of by galley to catch them with their good units on the marble. ah well. Yeah, aggress early and often, but you get +2 stability per conquest. Just make sure you whack Babylon first. And you won't have to expand beyond your historical boundaries really, so your stability should be fine. Just happily accede to the arab demands when they spawn - you won't care anymore at that point.
35 45 Greece Tec race and building cap. difficult for UHV
... This is the easiest UHV ever. Seriously, don't build settlers. You've got an amazing production/research city, and a UHV that can be done OCC style. Grab the required wonders first, then grab the great lighthouse, great library, leaning tower, etc... Whip infrastructure when convenient - the overflow will help your wonder mongering. You'll be teching like a bandit, and you can use the excessive number of GP you'll be generating to lightbulb stuff if you need to. After grabbing philosophy, beeline optics and sail away. Just make sure to adopt monarchy or you'll never keep your people happy.
I could probably comment on some of the other ones, but these struck me as in no way hard to UHV. The only one of those 4 that involves any luck is Greece, for whom the Oracle needs to not have been completed when you start.