I'll paste here some thoughts I contributed to a discussion @ Apolyton.
Viking way to victory? Get Relics ASAP, and return them. The English one starts in their coastal capitol, any Viking Civ can grab it around turn 5. The French one is in Paris, pretty near to the coast again, grab it around turn 10. You'll need some time before you have researched Seafaring, to get enough boats for the crusade, but around turn 45 you should have deliverd 2 Relics. Kill stuff, VP victory around turn 55 on Deity is doable.
Christians? Above Monarch, crusades aren't worth it. By the time you can reach the Holy Lands with Knights, Jerusalem will be beefed up with Pikes or even Swiss Mercs; 18+ on DG isn't unusual. The big problem you have is not the power to take Jerusalem, but the insane amounts of Curraghs you'd need - and Galleys come quite late. An exception is Britain, who starts with 2 Galleys and an Army; fill it with Swords ASAP, and grab Jerusalem before the Abbasids have Pikes. Sure, you'll need about 15k VPs more, but the headstart helps.
For any other Western Civ, Arabs, Constantinople, *do* build up Infra. Unit support really hurts. Markets are far away. Blacksmiths (100sp factories without pollution!) rule. Many Wonders are really useful; HRE obviously, but Bayeux (=Sun Tzu's; it's mostly one large continent except England/Norway/Sweden), Domesday Book (=Central Bank, but without Markets this one really shines) and Magna Charta ( free Courthouses everywhere + 3rd Palace!) are very strong as well. Contact everyone ASAP, the uber-Tech is Map Making; getting that first means something like all Gold/resources/ techs available! The Arabs and Christian don't play much different on the higher levels; you'll easily hit the 30k VPs long before you could reach Jerusalem anyway. Also, techs are worth a lot VPs; completing the tree gives 7945 VPs.
Muslims? Cordova, Abbassids: Just fight enough wars. Turks: Build up and take over the world. Fatimids: Very long build up - by the time you're done with that killing only the Abbassids will be enough to win.
Random notes:
* In this Conquest, the AI is capable of winning if you don't fight enough; Turks, France, Abbassids and at foremost Byzantium are your competitors.
* Assassins are surprisingly strong, once the AI shows up with SoDs of SwissMercs/Longbows (or SMs/ Berserks). And, if you attack a city with them, picking a Longbow, you also get intelligence about the defenders.
* The late-game units are pretty nice.
* The non-playable Civs have neither traits, nor UUs or free Techs, only 2 Kings and no Markets in their capitals. Exceptions are Poland (REL/MIL, Western Church, Knights) and Castile (Knights). Be aware that Poland for about 50% of the time builds the HRE, definitely no weakling! Others candites are France and Germany, rarely England. Never seen Burgundy, but once the Turks!
* The AI will never research the opening tech of other flavors before the 3rd era, but occasionaly steal one.
* Libraries and Monasteries are identical except for the cost, but since all Civs but Norway/Sweden/Denmark and Turks (who start with Arab Learning anyway) are REL, it doesn't matter at all.
* Fear the Plague.
* Despotism can be worth it for Fatimids, they suffer a lot from the unit support early.
Recommended Civs:
Germans, France. Norway (the other Vikings are too easy). Byzantium on higher levels (pretty boring below Emperor).
My favorite: Bulgars, Germans, Magyars.