Ok, I figured out the issue - the hard way.
tl;dr: I had settings / general / restrictions set to turn off Podcasts. I never deleted the app at all - when you restrict the app, it disappears from the home screen and won't show up when you search for the app in the Play Store.
I contacted Apple Support on twitter about this (which, by the way, was wonderful - very helpful and quick responses.) They asked me to back up my phone and then restore the phone to new, sign in to my Apple ID, and try to replicate. The Podcasts add was there, I deleted the app, it was the first option when I searched for "podcasts" in the app store and was easy to restore.
What made it the hard way: I backed up in iTunes, using the same encryption settings that I always do. I assumed that the iPhone backup password in keychain access was the backup password. Well, when I tried to restore my phone, I discovered that it wasn't the password, and, as it turned out, no matter what I guessed, I couldn't restore my phone. I did have an iCloud backup, but that was telling me that it was going to take 4 hours - then 5, 6, 7, 8, and finally 9 before I gave up. I couldn't wait that long.
It wasn't until later when I was going through settings that I found that the podcasts app has a restriction setting that both removes the icon from the phone and prevents the app store app from finding the app on the App Store - that was why I couldn't find it before.