I honestly see the most potential in opening piety with the Mayans. Half speed pyramids sound good to me. However, if I was playing the Byzantines, I would open tradition then aristocracy for stonehenge, then go into piety.
I think I'm with you on the Mayans. I'm picturing a Mayan empire able to build those Pyramids at double-speed, then Temples, becoming a faith-generating powerhouse. Then grabbing the Jesuit reformation belief and using all that faith to buy the higher-level science buildings, and just crush everyone technologically. Though the last time I played as the Mayans, I went wide thanks to Liberty and fast Settler production, taking advantage of Messenger Of The Gods for an extra science boost. With the science penalty you incur when adding cities, it might be better to go tall instead. Does the faith cost for a University etc. increase the more you build them the same way it does for Cathedrals & such?