Find an email provider that provides decent support, i.e. you can call and talk to a real person. Make sure they support 2FA (ideally the non SIM variant). Also recovery tokens that you can write down and stuff like that.
Personally I run my own mail server but I understand that's not everybody's cup of tea.
And if not then why not? Is it because Google is a bigger and more obvious target or something specific they are doing badly?
If you think people should switch then these are the kind of questions you should answer.
This would happen with any email provider.
So the fix isn't changing email provider, it's using a more secure second factor, e.g. U2F.
source: I work at fastmail. It's cool.
I am mostly just suggesting that folks who read stories like these and fear similar predicaments take the time, effort, expense, etc. to properly secure whatever accounts they have.
Thought experiment: if someone steals an account with no 2FA, enables U2F and other security mechanisms, how will support verify who truly owns the account? Or the reverse: user enables U2F and someone calls in and tries to claim the account was stolen?
Having humans make judgements is important because the real world is complicated and people are imperfect, but using U2F in the first place can save you a huge headache, no matter what services you use. If support can just flip a bit and disable U2F, it isn’t very useful for the same reasons accounts get hijacked to begin with.
And those things? It comes down to having strong process rules and having intelligent life forms make the decision.