Google mail is still technically in beta, but I've been using it for a year and think its awesome. Over 2 gig of space, ZERO banner ads, and lots of notification tools like systray notifier, to show you when you have new email ( like yahoo messenger ). PM me your email addy, and I will send you an invite.
If you want to sign up now without an invite, you have to give them a mobile phone # which supports Text messages. They send you a code, and then you can sign up yourself. I don't know what they plan on doing with your mobile number..hmmm...