Of course, I should have mentioned that I want to be able to access my emails from any computer, with the peripatetic lifestyle that I lead. That means webmail, doesn't it? Or is the distinction between webmail and fixed-to-this-computer email not so clear-cut nowadays?
Fixed-to-this-computer email hasn't been since IMAP was invented. (Well, you could do it with POP, but that got messy quickly, as it generally meant leaving all the mail you'd ever received cluttering up the single inbox.)
IMAP allows you to store your mail in folders on the server, such that any changes to folder contents are reflected in every client you use to access it. It does require that you have a mail client and that it's configured correctly (a process that's much the same as configuring a POP client), which means that it's only realistically something you're likely to want do on your own computers (or at least your own account on other people's). In other words, it means you can happily use Thunderbird or Outlook or whatever to access your email on your desktop, your laptop and your sufficiently standards-compliant smartphone without stranding messages on any one computer, but it's not something you're going to do from a random cybercafe or friend's house - you'll still want webmail for that.
Pick a provider that gives you both IMAP and webmail and you've got the best of both worlds.
I also recommend registering a domain of your own for email purposes, from a hosting company that will provide a forwarding service for email if you don't want to get technical about it. Means your email address isn't tied to any one provider, which makes life a lot simpler when you decide to change.