Fastmail for me. Switching was easy. For existing services/logins, I just added forwarding from gmail and didn't bother changing addresses except with the most important things. Most services from back then no longer exist anyway, or have turned into spam, so I eventually turned off the forwarding.

I don't yet pay for search (mostly using duckduckgo), though I am considering it.