It is worth noting that these don't support IMAP and Contacts/Calendar like most email services do. (They say that it has to do with how they handle their encryption)
IMAP on Linux does work as well. It's a stable beta. I use it w/o any issues.
Thanks for noting that. Strictly speaking, email doesn't include contacts and calendaring, but it completely slipped my mind and I had already shortlisted Tutanota.