I chose the Celts for my first BNW game, since I really liked using them in G&K. I think they still have a solid religion advantage, but if you want to fully utilize it, you still have to fill out Piety early, like other civs. In my game, I founded the first religion well before anyone else, in part thanks to Desert Folklore, but something like four other civs apparently opened with Piety and got Reformation beliefs while I was still finishing off Tradition. Those seem too powerful to resign yourself to picking through what's left, but you're still in pretty good shape if you get first pick of all of the other beliefs.
On the plus side, barbarians seemed a bit more numerous and aggressive, which gives more opportunities for Pictish Warrior faith kills without going to war, especially since it's more worthwhile to research Bronze Working early on. And the Ceilidh Hall is as good as ever.