I've tried multiple machines, multiple iTunes versions, multiple cables, and ports.
My phone was originally rebooting randomly. Thinking it was an electrical short problem, I put in a new battery. That didn't help, but made it worse. I tried the old batteries again. No luck. Eventually the phone would just hang at apple logo.
Restoring it gets it stuck in "Waiting for iPhone" with an apple logo with an empty gray bar under it.
Likewise, DFU mode restore gets it stuck in "Waiting for iPhone" with an apple logo with an empty gray bar under it.
Not jailbroken. No water damage. Was not dropped.
Best Answer
Well, shave my whiskers, crumble my biscuit, and oil my gears, I'll be darned!
I let it sit there in that state for a literal hour (72 minutes) with no progress bar or evidence of activity [even over USB 3.0!] and it eventually restored and booted. I still had to go through some prompts to get it to connect, but it worked.