The biggest feature at launch was the idea of "unlimited" storage (I think at the time it was 1GB) This was a huge departure from the existing Yahoo!/Hotmail models which had much more restrictive limits on storage.

That and the idea of one inbox and no folders. The concept of letting your mail flow into one box and not "filing" it was also a big change from the existing mindset.