How to build hard-build Petra on Immortal/Deity?

I still want a really early NC preferably by turn 100, but I really want the OP Petra wonder as Morocco. Is this possible or does beelining Currency put me too far back in science? I figure I'll have trade routes going so that should compensate early beakers lost from skipping out on turn 80 NC. Thanks.

Try to scout as best as you can. If no AI has desert near their capital/1st expo you're good for a late Petra (AI will eventually build it if you give him too much time even in a small expo with only 1 flat desert tile)
If you see Desert near a capital (or if Desert Folklore has been taken as a Pantheon in case you can't see every cap) you better beeline it and have great production (probably marble and plenty of salt) at cap to have a very small chance of grabbing it.

I have built it in the Spanish DCL game on T65 I think. But it depends, as Bob said if AI has a desert capital then it is hard to get it first.

You need luck definitely. I've built it in the DCL6 on turn 82 and I've done it on DCL20 on turn 65. If you don't have at least 3 hills I would definitely advise not to even try it. Optimally you'd want to sit on gold/copper so that Mining tech would help you in both production and happiness during the expansion phase. That way while you shift your citizens to work those tiles, you can even pile up some gold, and if you have enough, you can consider buying a caravan and sending it for a temporary boost in science.

Either way, if there's a Civ in game which settled on desert and has a flavour for wonders, you have your work cut out for you obviously

It usually is easy to get on immortal. On deity however it can sometimes go at turn 60 and there is nothing you can do about it. But if you see someone that might get it I suggest DoWing them, it might give you the extra turn necessary. The safest way to get Petra while still having a good science is to make a fast external caravan, get 2 cities + writing and then go for currency first. This is the best compromise in my experience and can give a turn 65 petra. If you want the safest just go straight for currency. If you want to be riskier but have the best science you'd have to go NC first and this will give you a turn 75-85 petra which is very risky on Deity.

You can also bribe another AI to DOW the offending civilization. Its easier for me to get Petra on Deity if I'm in a situation in which all Embassies are in place (i.e., Terra or Pangea). You can pretty quickly see if someone's starting a build and bribe for a DOW. On Continents I find it luck of the draw. Good comparisons - I bribed two wars against Wu in the DCL 20 to prevent Petra, but I could not stop a cross continent Petra build in DCL 6. Went on T67, wooooo hoo.