Linux

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.

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.

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

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.

So, you need a groupware/email provider and app recommendations?

Thunderbird will likely be the most recommended client as it does all 3 of the things you need. So, it gets points for being easy. And you can try it out on Windows before to see if you like it.

There are other OK clients. Overall I am not a big fan of Thunderbird or most of the other options. I settled for Claws, but it is not for everyone.

Proton is highly recommended, along with Disroot and Tutanota and Mailbox and many others.

As for Android syncing, it is all pretty easy. I use Mailbox and on my Android FairEmail, Davx5, Icsx5, and Etar to keep everything synced.

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

Why not try 365 with thunderbird?

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.

Have you tried Thunderbird? It comes with a calendar and has recently had a visual overhaul

Check out onlyoffice. Open source MS 365 alternative and yet to find any issues with it.

https://www.onlyoffice.com/

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

Use your SSON credentials on https://office.microsoft.com to have all the office products in a web variant. Those are pretty good actually.

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.

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

Try thunderbird

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.