Linux

Lol wut. Use Thunderbird. We rolled that out to everyone at work.

If you're (going to continue) using Office 365, you can use Evolution as an Outlook replacement. Evolution EWS rides OWA and ActiveSync protocols to give you email, calendars, contacts, notes, etc. I've used it for over a decade. It works very well once setup.

As for Android, there are several, including Outlook for Android (which is bloated and slow, being a Microsoft product), which I am forced to use because of our company SSO config.

If you're looking for an Office 365 replacement, I use Nextcloud for my personal stuff. It has files, contacts, calendars, notes, etc. If you install the OnlyOffice plugin, you get multi-user online document and spreadsheet editing. I use the DAVx5 connector to get (shared and personal) contacts, calendars, and tasks in my Android phone. It integrates into the environment so all calendars and contacts apps work automatically. It also automatically backs up pics/vids I take with my phone automatically.

Why not try 365 with thunderbird?

I've been on Linux desktop (Mint) for over a decade now. My company uses O365 for email, as did the organization before them.

I use Thunderbird with several add-ons: Mailbox Alert, Owl for Exchange (paid), Provider for Exchange ActiveSync, and TbSync. I honestly couldn't tell you which one or ones I find most useful - it's been so long since I've installed them, I don't remember which addon provides which functionality. My most recent install was Owl, for calendaring and because things got a wee bit fucky with O365 servers for a week or two last year. I have Thunderbird set to collect addresses when I reply to users. You can have it query AD for contacts, I think, but it tends to be a wee bit slow.

On my Android phone, I use the default Google Calendar app, and the Gmail app to query O365.

If you don't mind self-hosting stuff, nextcloud with davx5 could be a great choice.

In my opinion, Tutanota https://tutanota.com/ is a better choice than Proton, there are apps for Linux, Windows, macOS, Android iPhone, working nicely together.

I have Microsoft Exchange for work, so I use Evolution client in Linux, because it supports Exchange properly. For personal mail I use Fastmail, it can synchronize to any app you want both on Linux and Android.

The absolute easiest way to sync all of that to Android is to use Google services like Gmail, Calendar, Contacts etc.

No other service will sync that to the built in apps.

However if you're happy to use 1 app for all that, the Microsoft email app should sync all that. Microsoft Outlook app

Fastmail is well-regarded, although they are hosted in Australia (which has some really dumb privacy laws). I use them. There's an import tool.

If you are privacy paranoid, mailfence is hosted in Belgium, which is a brick wall when it comes to privacy and warrants - likely the best jurisdiction in the world in this regard. The interface is dated.

Other then email. Nextcloud checks all those boxes. It is how i sync my calender and contacts with my devices. Including android.

Just in case you don't know, you can use those Microsoft services no problem in Linux through a web browser. You can also "install" them since they're PWAs and integrate them with your system notifications.

There's also Thunderbird from Mozilla, and the open source fork Betterbird that has a far more modern appearance and options. That will work easily with your existing Microsoft email.

I'm by no means encouraging that you stay on Microsoft, but moving to Linux AND changing providers for important stuff like email and calendar might be a lot all at once.

Google Mail/Calender/Workspace or what it's called. Works perfectly in a web browser and you can connect Thunderbird or Evolution. Most people who use Linux professionally are on Google. And most other people, too. Microsoft is a niche player unless you are locked in.

You can add self-hosted and open-source stuff anytime, but you'll need good email and calender that plays nice with the outside world, so Google. Maybe something like mailbox.org. Maybe you ISP's email + Thunderbird + nextcloud + K9 on Android will do, but you do not want to self-host or experiment with email if your business relies on it.

Nextcloud works fine for internal file exchange (but so does google drive), internal calendar, many apps on top of it. It even has a web-based mail client, but personally I would not use this is as my primary business email unless you are a hosting pro.

Because you are just looking for an email provider: https://disroot.org/en (donation financed) Otherwise there are paid providers which are based in germany: mailbox.org or posteo.de

Maybe check out Infomaniak, there's also a cloud drive option and integration of onlyoffice desktop editors.

Try thunderbird