I want an email client that can download all of my existing Gmail emails and then i can search for them quickly. I have tried Thunderbird, Mailspring, Clawmail, Geary. Some of them can download all of the emails, but when it comes to time to search, they often freeze. Thus, I would then need to do the old fashion way: open up a browser and login from there.

Is Mutt ok with such requirements? Any other alternatives?

I also use GrapheneOS on my phone. Before I had Fairmail for my Gmail account but the search feature is quite buggy. So.... even though i know it is shitty, I have to use the official Gmail app for my Gmail stuff. It gets the jobs done: i can search for an email 3 months ago or follow up on an old email thread very quickly.