Wayne,
I'd reccomend
www.fastmail.fm - you don't get huge amounts of storage but you do get a very slick interface which loads really quickly and is very well laid out. You get IMAP access as standard with a guest - free + ad's account, member US$14 ish one-time only payment, no ads 10MB ish storage. If you want POP access then you pay extra for that, upgrade to full service is USD39,99 a year then you get 150MB storage. IMAP is better anyway. Web based access or configurable through Outlook Express / Outlook. Point is it is a very good service and I'm happy with it.
The interface is a lot slicker than Gmail by the look's of it, can be "skinned" as well with templates that they provide.
if you do sign up, enter my username
rockrabbit@fastmail.fm as the referrer. Cheers, Steve