[real time search ongoing]
Goodness how have I not known this?!
I recall seeing it as sluggish and awkward when I finally decided to check it, abusing Ajax. Other web interfaces (that I tried) were more lightweight and predictable, and regular mail clients I found to be a much better UX. So I've mostly attributed Gmail popularity to Google promoting it, possibly using that invite-only policy to make the users to spread the invitations. It sounds like at least some users actually liked it, but I don't think it's a clear example of a good service by Google.
I recommended people use Google in part because there was, at the time, less risk of them clicking on something and being confused by it. (Why is there news in my email? Where's my email? How do I search?)