Hotmail provided just 2MB of space when gmail launched on 01 Apr 2004. They increased it to 250MB in June 2004.
I used Yahoo Mail at the time, which had a limit of 6MB (and IIRC that had been an increase at some point). Soon after GMail came out they upped that to 250MB. Searching now I find an article saying this happened December 2004. I seem to remember it happening closer to the GMail announcement though but I could be wrong.
(I got my first gmail account in 2004.)
Yeah, the UI wasn't bad, but there was less email back then and I didn't (still don't) really mind being served HTML repeatedly instead of some "AJAX" application, which is what I remember the technique being called. (It used to be the latency to the server was poor and JS hid that; now, on 2-3ms fiber, it seems that the JS actually introduces a lot more latency than it hides.)