I did a similar thing 2 years ago and chose Fastmail. Their web-app is best of breed ex google -- unfortunately, the honest truth is nothing is as good as gmail web + gmail apps + google cal.

Fastmail does have more issues -- lack of fit and finish, their web app is sometimes buggy, their spam detection is buggy, it's imap, the lack of gmail style conversations being the fundamental unit of work in the app shines through sometimes, the gmail app on android does not interact well with fastmail, etc. However, they have recently fixed my biggest complaints: charging 11 cents per sms message to do 2fa and their rules interface looking like it was written as a my-first-javascript project. So it's actively improving. I like it enough that I recently re-upped for another two years.

They do enjoy one big advantage over google besides privacy: tech support! Like a human, that reads and responds to issues submitted through their site! I've contacted them twice with questions about setting up my domain and one other thing and I got replies, from someone who knew what she/he was doing, within an hour each time!

Also, they will do a catch-all address (eg [email protected]) which receives email from every address not specifically defined. Thus you can implement the best anti-spam technique: every email you give out is [email protected] which forwards to [email protected] so you can tell exactly who sold or leaked your email address. eg [email protected] was sold all over the place.

I love fastmail. Really I do not like gmail style conversations so I prefer fastmail over gmail.

I too love the FastMail web interface. It rocks! On Android, unfortunately, FastMail comes up short. I have yet to find a satisfactory solution

I've had my mail servers at Linode for about 8 years now, no problems at all. If anything, I am more restricted on mail processing rules than anyone else.

Yes in theory all you need to do is update your SPF to whitelist Google's SMTP relay.

Silly question, but have you tried sending an email to someone running spam-assassin and check the headers of the received mail to see if there's anything obvious flagging you? For example, on Linode make sure that your reverse DNS for IPv6 are also set correctly.

I find it hard to believe that you get classified as spam for no good reason, unless perhaps that Linode / Digital Ocean are known for hosting so much garbage and people can be tempted to outright block them, but I doubt Gmail does that?