Replaced iPhone 4S batteries, won't boot, won't recover (even in DFU), iTunes says "Waiting for iPhone"
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.