We used FedEx last year, did not use priority/overnight, but the 3 day service. It took about a week to ten days, if memory serves, to get to Austin from Glasgow. Some of the delay was particularly vile weather in Indianapolis, the FedEx hub.
I don't e-file because I'm taking advantage of the exclusion of social security from US taxes. There is no way to put that into the appropriate boxes (instructions are to write "per US/UK tax treaty Article 17.3" it on the line next to the box stating zero taxable ss) on any of the free online services I've seen. That, of course, may not be an issue for the OP.
I'm also not keen on paying more to a service to e-file than it would cost me to send via FedEx, which eventually does get there.