The Google Podcasts app has search like that on Android as well. I agree that it's amazing that there is such a dearth of usable podcast apps out there, especially on Android.
The problem there is you need to install the Google app in addition to the podcast app, something I refuse to do. I just don't get why podcast search is so appalling, and why it's not a bigger deal. It drives me bananas.