It really looked like I had bricked it. In desperation, I looked to a program called iRecovery, which is designed to get the phone out of recovery mode without doing a restore. That didn't exactly match my problem, but figured it was worth a shot. Getting iRecovery working in Windows 7 seemed impossible, so I just installed it on an old laptop running Windows XP. Running iRecovery in shell mode, I see lots of error / warning messages, notably this:
gas gauge read timed out
Hmm. Googling this error message indicated and issue with the battery. I found a new battery for $7 off eBay, and sure enough, was then able to restore IOS and get the phone back up and running.
This was a good 3-4 days of frustration. Would have nice if iTunes (or RedSn0w) indicated a battery or hardware issue, but both kept pointing towards software as the problem. Anyway, thanks iRecovery - without you, I would have never figured this out.