This changed when they were the first folks out there to get a dynamic interface in the browser (some of you may fondly or not so fondly remember the days of DHTML, XMLHTTPRequest, and the like). Fast forward 10 or 15 years and now GMail is the standard by which everything else is measured.
I'm sure there are some things that are objectively better, but a surprising amount of preference comes from familiarity.
Just install your favorite desktop + mobile mail apps and you're fine.
If that can't be done with Protonmail, and you want to move your email out of the US, suggest FastMail, based in Australia.
Nothing really support IMAP search.
Every mua sucks at large mbox file.
-- Edit: I am a happy fastmail user
But I guess you mean search w/o local caching