In case you haven't heard about gmail, it is Google's free web-based email. You get 1 GB of storage space (that's about 1000 MB), or four times as much space as hotmail. Also, it has a really nice interface, and no annoying flash ads. Personally, I really like it. You can read more here.
Oh yeah, and you can search your email like you search Google.