I recommend gmail. It has its faults, and there is some politics going that some disagree with. But Google is going to be around for a while, yahoo and micosoft/MSN/hotmail are probably going to shutdown, or at least really pull back on on the available services. Most of yahoo's employees don't even use yahoo service. Gmail has far fewer problems than any other provider I've had to deal with, and I'm wondering what problems Uffda is running into.
If you don't want to use web-based services, you can use something like thunderbird to manage your current email. There are other, better clients as well, depending on your needs (multiple device support, multi accounts, encryption) although a lot of them are open-source and require a fair bit of knowledge on the part of the user. I would avoid Outlook, unless you are already frequently using the rest of the microsoft office suite and are really comfortable with it, it is just painful. If you think Gmail slows things down, Outlook will make you want to burn things. Besides, if the main servers go down, that still means your email doesn't get through, no matter what method you are doing.
Keeping in mind that your provider (the @whatever.com) and your client are different, and if you want to change providers, you will loose your address, which might be a problem.
For those who are having trouble with Gmail on a slow machine or connection, click the "view in basic mode" or similar right as it is loading. it cuts out a few features, but if you like it, you get the option to default to it.