Also, I got the one start that didn't have a good pantheon, heh - Ivory.
I still ended up building a powerhouse religion with Faith from Forests, of which I worked about 4 total until things got rolling, with Cathedrals, and +2 faith from amphitheaters and Opera Houses (which as it turns out, is pretty absurd), with the usual Tithe/50% faster spread.
The Honor Opener, Warrior Code, and the Piety opener are basically too good to not take. The extra policies you get from the reduced culture costs should all go to there, because it makes it so that you sacrifice nothing - you obtain a ridiculously powerful civ in growth, culture, military and religion for a very minor investment.
As far as difficulty goes, I was just doing what you recommended - dropping a difficulty from what I normally play on
I can win at Deity, but it's more effort than I like to expend, so I play at Immortal where I can not micromanage spies and stuff and still be okay. I was pretty shocked at how Emp has gone for me. I got a T88 Attila win yesterday, and now this tech tree game has been a complete joke. I will try out Immortal this week/next weekend and see how it goes, but so far, I can basically say if you're looking for a challenge, you definitely shouldn't be playing anything lower than you normally play on, the AI is pathetic and the bonuses appear to be balanced to give you a chance in Deity. Against non Deity AI, you're just gonna crush them if you have any idea what you're doing at all.