My first playthrough was years and years and years ago, but let me see if I can piece it together in my head . . .
1: Charnel - His personality, choice of words, and style really resonated with me.
2: Stratos - I originally tried to go Charnel for mission 2 as well, but I remember the Demon Gate of Golgotha mission being WAY too hard for me. I figured I'd try doing it from the other point of view, to maybe get a better idea of how to complete the mission, only then discovering that Stratos had a different mission in mind for me.
3: James - The warning about Jagudar seemed too pressing to ignore, so I dropped both evil masterminds and went to try and stem the tide of the Cult of Ashur. I'm no fan of Soul Mole or the Taurock, though.
4: Charnel - I decided I wanted to see how good ol' Charny was doing. Boy howdy did I ever pick the right moment to return! Animate Dead: HELL YES! As I recall, I ended up on the exact same map as I was on the previous mission too.
5: Pyro - At this point I don't think I had many options, so I wanted to try something new. I may have served Charnel again at this point, though. I can't rightly remember with perfect clarity.
6, 7, 8, 9: Charnel - I proceeded to finish the rest of the campaign under Charnel's banner, and was pleased with the ending. I vaguely recall defeating Yogo before Charlotte died my first playthrough, so in my mind, both James and Charnel had survived to the end.
Grand total, I've easily done over 20 playthroughs, including pure playthroughs for each god. My favourite custom spellbooks start with Stratos, and include Animate Dead, so most of my playthroughs account for those two particular elements/missions. There are some mission which are DEFINITELY too hard, but all are still possible to finish. One of the few complaints I can honestly fault Sacrifice with was a poorly balanced difficulty curve.