Thanks for all the suggestions. I'd take TK if I could, since I took that route a few months ago, but it's not offered on the day I want to leave.
If I end up with two different PNRs (E.g., through MUC), would UA route my luggage all the way to DOH (including an xfer and layover in IST)?

And yes, that DBX flight out of EWR looks bad, at least when I looked at the recent history, but then, I cannot book the connection through flydubai through my TA, so there's that.

Looks like MUC and FRA don't help you stay on *A as you would have to fly QR to DOH from there. Not sure if you could interline your bags, but you would certainly need one ticket for any chance, in my mind (really old thread on interlining with QR - https://www.flyertalk.com/forum/show...ferrerid=17958). UA.com pushes you to DEN-FRA/LHR-IST-DOH or DEN-FRA/LHR-CAI-DOH if you select a day where TK isn't flying. That would be on 1 PNR. If you dump *A, you can do a 1 stop via ORD or DFW (AA/QR). I guess you could do separate reservations UA to ORD/DFW connecting to QR to DOH.

If you need to leave on a day that TK doesn't fly from DEN, perhaps your next best all-*A option is DEN-ORD-IST-DOH.