The first scene releases of mp3's were in 1996[0]. It was 1997 when things got rolling, just as Winamp was released.
I recall then that even new PC's couldn't decode at full CD quality and you had to downscale. We also picked which songs to download locally based on their size
Spiderbait's song "Calypso" was probably the most popular mp3 download in '97 since it was only 2.5MB and a lot of people just wanted to try this new mp3 thing everybody was talking about.
The decoder Winamp used was actually amp - developed by Tomislav Uzelac[1]. I can't remember how he dodged patent issues, but he had his name and an ask for donations in the about box of v1 iirc.
Winamp owe a lot to amp - the first version was essentially a skin + port of his library to Windows. I'm pretty certain Winamp v2 also used amp, just as it was blowing up to become the most downloaded program online.
Nullsoft and Justin were absolute legends. He wrote an AOL ad removal / blocking tool and WASTE while at AOL. I can't think of any similar startup or subsidiary today that has even close to the attitude / courage they had.
[0] https://www.mp3scene.info/releases/year/1996/
[1] https://en.wikipedia.org/wiki/Tomislav_Uzelac