Determine if they actually want a *good* premium economy product and service - or just more legroom.

If it's just more legroom, then there's probably some availability on those AA and DL flights. You'd just search regular coach fares and select the seat assignment as an add-on. A search engine that looks for true premium economy won't show any U.S. carriers (yet).

If they do indeed want a full premium economy experience, then they'll need a European carrier and a connection at their hub. If you're going to search fares on true PE, you might as well search J fares as well...never know when you might find a discount-J fare in the same ballpark as PE. (I can never fully predict when J is going to be $3,000 vs. $1,200 each way, but believe it or not $1,200 sometimes shows up.)