Well if you have UA miles you can upgrade on Lufthansa. You can even use a SWU on LH now. Just book it as a UA codeshare. DL miles should help on AF and HP on BA.
If you can't upgrade, think about flying Saudi Air as they have very roomy 777's and hopefully not too many people on the New York-Riyahd run.