I'm also a veteran of Civ 4 (didn't bother with 5) and Gal Civ 2
I would put the learning curve more toward the Gal Civ 2 than Civ 4.
I've been playing for about a month on the beta's and so far every game I've played has been very different. It took me about 3 ~ 4 games to get the basic's down... I'm still trying to figure out all the cost benefit of choices... there are just way too many possible paths. I havn't even touched the Empire or high majic factions yet, (mostly focusing on Kingdom and more often than not quest based victories)
Choices aren't too hard but there's definatly more that one path to victory.
AI' opponents are seriously a pain in the butt in early and mid game... If I make to end game (yes the AI has beaten me a number of times) it tends to not be much of a challenge but the variety quests more than keep the end game somewhat entertaining.
Starting position and map randomization plays a Huge factor in your strategy and that changes each game. if you have not much iron resources in your territory don't expect to build speciallized superstacks to conquer all commers. similarly if you dont' have crystal or horese then other types of units are going to be tricky.
Mana is also highly variable and can change your strategy dramaticly.
Each faction also has a high degree of customization needed. building mass archers with Tarth is a good strategy, and is rather stupid if your Resolin.
the moddability is also quite high which should make it fun as users create the usual suite of fan fantasy based mods (I suspect someone already has a Fire & Ice mod buidling, and I can see middle earth, mistborn and wheel of time right behind those)