I just migrated away from Tuta after trying the service for a year. I like it well enough, but it presented too many frustrations to be a service to pay for.
- While they have labels (yay!) their inbox rules cannot apply labels so you are stuck manually tagging everything (boo!) - and the UI for manually tagging could use improvement.
- Mobile (Android) notifications stop working frequently.
- While they integrate their contacts in to the Android contact list, they refuse to integrate their calendar with the Android system calendar - meaning I cannot pull a consolidated list of calendar events in to my launcher, and am stuck using their calendar application (which could use a lot of improvement).
- If you set a calendar event reminder, and then change the time of the event, the reminder will go off at the original event time (or 15/30 minutes before, whatever you set it to).
- Long refreshes when loading the inbox. Navigating back to the application often has the server disconnected, then you have to wait a spell for it to reconnect so you can carry on.
After searching around and checking purelymail, infomaniak, mailbox.org, mxroute, migadu, zoho, etc. I landed on fastmail (with my own domain) predominantly because of their implementation of labels (super slick). Their mobile app and desktop applications are also very slick. Contacts/calendar sync in to the Android System is done through DavX, but I also have it syncing to my Nextcloud instance. It's a more expensive solution than the others, but labels (tags/categories) are such an important part of my workflow that there aren't a lot of options unless I wanted to go back to M365/Google Workspace.
If I was to give up labels, I'd probably go with infomaniak or mailbox.org. Both of their offerings were slick and the price was right.