I voted for Gmail. With my Yahoo account, I had been unable to log in for like three or four times until I sent them an email for recovery. Well, I know it's free but it's a terrible experience anyway.
I totally love GMail!
While I'm not an active Mail user most of the time, I can use the gmail account as a hub account, letting it fetch all POP3 mail on other accounts I have around and download all of it using KMail, so I only have to configure my client once and gmail does all the dirty work.
Also, it is very less intrusive (not like hotmail) on my sent mails and I can send mail also with the other accounts from the same on XD