I've recently started to move a lot of the services I use away from Google provided services. Who'd you go with instead of Gmail for email?

Not OP, but I moved all of my email from free Gmail to paid Fastmail about 2 years ago, and I've not had a moment of regret.

I send quite a lot of email for work and other things and I have what I think is a higher-than-average number of email addresses to manage.

One adjustment I made - I now archive older emails to avoid extra storage costs, which in turn means that searching for older emails is slightly more hassle.

Fastmail's web interface and mobile app are not quite as slick (as gmail) but this isn't a big deal for me personally.

Can't you just use another e-mail app, like for example K-9 Mail, with it?

I used K-9 for many months and it was just OK. The FastMail app was not a huge improvement (over K-9) but it was still an improvement, at least in my experience. From memory K-9 didn't handle multiple "send-from" accounts as competently as the FastMail app, and there were other quirks that became more irritating over time.

I went with Fastmail. Great service with an excellent customer service. I feel confident that if something were to happen to my account, I wouldn't lose it forever.

I set up my own mail server. It took me a few hours with a few minor hiccups along the way, but after contacting Microsoft and AT&T to get my IP removed from their block lists and asking family and friends to mark my emails as "Not Spam", I am now in control of my email and it feels amazing.

I have also taken the time to run my own calendar and contact services.

For mail, I run Postfix and Dovecot over SSL and access email from my iPhone or web browser using Squirrelmail.

For contacts and calendar I use Baikal.

> after contacting Microsoft and AT&T to get my IP removed from their block lists

Yikes.

Isn't this exactly the problem with running your own email setup? And have you not found that keeping on the white side of mail server lists is a constant and moving target?

May I ask, do you send a lot of mail and have multiple accounts? (I do, so this overhead would be impossible for me to manage personally)

Fastmail here. Migrated a couple of years ago, never looked back.