The other convenience Spotify over Winamp is that you don’t have to find and download MP3s, you can just type something in and 99% of the time just start playing it immediately...
Spotify's real innovation is not music streaming. That technology is not new in any way. The real innovation is the fact it somehow obtained the licenses necessary to legally stream the music people wanted to listen to.
Finding and downloading mp3's isn't a problem.
Do you really think there's no difference there? If you get a text from a friend saying check out this song and you're out and about on your phone, are you really saying that somehow downloading an mp3 to your phone is as easy as spotify?