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.