I once got three in a row on deity, so they're definitely there.

I won that one too, one of very few deity games I've played to completion. Bad ass luck is bad ass.
If you don't have another side in the game that will rush FOL, it shouldn't be hard to get it. Don't switch while weak though, founding it is good, spreading it is good, switching to it without the holy site built and enough of an army to deter an attack... suicide.
It's a much better religion to be as an elf, you want to get the benefits of shadows, but you don't need to actually switch to COE for the boost of having it in your cities. I've never been able to make it without a religion founding, too much coin from the holy site to pass up the opportunity, COE is late, very late. By that time you're usually doomed if you haven't already made a play for someone's turf.
My best Deity win was as Khazad, I stuck to my capital, founded kilmorph, got arete out, popped the wonder with an engineer, and walked all over the goblins with a shitload of highly promoted axemen and Bambur. War can be nice, especially against an occupied opponent.
Don't be afraid of declaring war on an enemy of the stronger AI, you'll end up at war with one of them anyway, and probably fast.
Hmm... Come to think of it, my advice may be useless. When I'm playing deity, it's with aggressive AI on a small map with six players crammed into it. Never tried it without the agressive AI, they tend to declare war on each other rather quickly, it might actually make the situation easier, but who knows.