Would a European phone shop be able to do better than their American peers? I obviously don't have time for them to ship the phone off for repairs and wait for it to come back.
The local shop here (Amsterdam) does overnights, but only in special cases - and they do it by sending you directly to the repair shop.
Is there any chance my European warranty might be useful for me?
There is a chance, yes.
Could I get a shop to upgrade the software without charging me?

Possibly. Worked for me.
Would I need to be in the country where the phone was originally purchased?
Only if it is a country-specific model.