I use AntennaPod from F-Droid, and it has the following search options, in this order: Apple, fyyd, gpodder, Podcast Index.