I’ve seen a lot of praise for Kagi, and perhaps one day I will pay for web search. I haven’t succumbed yet though.
I haven’t had any issues using non-Google search providers on Android, I use Firefox {or rather, Fennec) as a browser where I can set the default search engine; and FF comes with its own search widget that uses the same default setting.