This has been my favorite mod in BTS (and I'm a FFH player who was greatly anticipating Age of Ice).
I played on Prince and as I recall, it took about 160 Papal favor points as Charlemagne to get that victory.
Charlemagne probably has the best starting position. I began with 3 cities with 2-4 pop, 2 workers, a few improvements (no more than the cities could work), some resources connected with rivers and roads, and some Chariots for exploration. It seemed to work well, as I was able to skyrocket ahead in points. Going for Papal favor is definitely a good investment, as the Papal Pikemen are very solid (8
+100% vs Mounted, +35% City Defense, I think) and come pretty frequently. Also, having two Nonchristian civs on my borders (Saxons and Bavarians) allowed for some early warfare without angering the major powers or upsetting the Pope.
Most of the other civs (AI) built only 2 cities, and they seemed to use more points to increase their population, build improvements, and to build units. I'm not sure that this was a better tactic. I think the scenario would be more interesting if the AI was a bit more aggressive. I did give gifts pretty eagerly, but I never once had another major civ declare war on me, except when I accepted a vassal who as already at war.
I do have one major complaint: there is really no reason to research and build the Swordsman units, given how easily you can get Macemen and how much more that technology has to offer. I would have like to have Pikemen, Macemen, and Heavy Swordsmen all be uniquely useful. In the end you're going to prefer Macemen as Pikemen and Heavy Swordsmen are weaker and their bonuses are too circumstantial and small respectively to offset the difference.