I finally finished the first mission with Persephone and it seems I'll have the option to choose a God's side each mission. Now I understand this will impact the storyline which is fine but I would prefer to pick a sort of less complicated road by sticking with easy missions first and then gradually increase them with harder instead of mixing them.

How should I proceed?

Personally I found the Persephone was the easiest way to go. While the first few units are a bit puny, all the early levels are simply a matter of guardian your units to a manalith, soak up the souls that get left behind from the attacks, then slowly move one.

However later on, and especially the final level (where you get the charm spell), you get some invaluable spells, which make the game easy to win.

I know you've asked about the early ones, but I'd really recommend your first 5 play throughs just being total devotion to a particular god, I get the feeling the units were partly intended that way. Customise later play throughs.

Not to mention that rainbow heal is widely considered one of the most useful/cheesy spells in the game.

I consider playing James exclusively the easiest way to go. The Boulderdash in the late game is incredible and Bovine Intervention gibs the target so no need to convert, just be there before the enemy wizard to the collect! Charm is excellent as well, but I prefer to add more Boulderdashes to my army. I also really like Halo of Earth, a nice way to add additional stopping power by just rushing your target..

No one mentioned Charnel's 4th level spell, Animate Dead???

That's the spell you want to add to your custom spellbook!

Most abusive spell in the game next to Persephone's Healing Aura.