The issue I have with picking from the start is it removes the "organic" element to the process. I think there is a way to reconcile your concerns without requiring everything to be pre-chosen.
It's not all pre-chosen; you choose your primary god at the start, but as the game progresses you'll add minor gods to your pantheon, each of which brings in an additional set of bonuses. Once you get to the point where you have four or five minor gods, their cumulative bonuses will easily outweigh your primary god's effects (at least until you reach Monotheism, at which point the minor gods start tapering off).
If you've ever played the original Age of Mythology game, it followed a very simple design. If you played as the Greeks, then you followed Zeus, Poseidon, or Hades. If you played as the Egyptians, then it was Ra, Isis, or Set. And for Norse, you followed Odin, Thor, or Loki. Each of these had a significant effect on your empire, unlocked a couple unique units, and so on; all of your normal units and buildings were determined by the race you were playing (which meant the Pantheon you followed). So Zeus followers would begin the game with more Favor and generate it faster, his infantry would be a bit stronger, and he could throw lightning bolts; these wouldn't change over the course of a game. Poseidon, instead, would get some naval bonuses, cavalry bonuses, and would have Militia units appear when a building was destroyed. And so on.
But as you played, every time your civ advanced to the next era (three times, assuming you didn't lose quickly), you'd pick one of two minor gods to follow. Each civ actually had three minor gods at each level, but which two you picked from would depend on your primary god. So if you followed Zeus, then at the Classical Age you picked between Athena and Hermes, and Ares was unavailable, but Poseidon followers would pick between Ares and Hermes, with Athena unavailable, and so on. Since these minor gods unlocked very significant abilities (custom units, custom promotions, custom god powers), they'd have just as much impact on your gameplay as your first choice.
That's the dynamic I'm aiming for here, although shifted from the RTS design over to a more intricate mechanism than just picking from a few preset lists. I do NOT want to recreate Civ4's religion system, I want to recreate AoM's god system.
Your choice of Pantheon controls your Favor generation methods, your major god controls the first set of bonuses you get (and the ONLY set of level 4 bonuses you get, since minor gods can't ever get that high), and these are set from the start and won't change. But the minor gods you add along the way, through the Mandala screen, will have a big impact on how your civ plays and you'll have quite a few of them by the end; while your choice of main god will have a significant impact on which minor gods are available, the dominant factor will be your decisions at certain Events that'll pop up from time to time.
I'm hoping to have the basic framework in place within the next week or so; I'm rearranging the techs now, and over the weekend I'm going to try putting in the first pass on the buildings (it's a LOT of XML). Most of the Lua is in place now, I just need to make sure it works. So hopefully by next weekend you'll be able to see for yourself what I'm trying to do.