cdda2wav seems to have existed by 1996.
the "quantum bigfoot" 1GB-and-up HDDs also in 1996 could hold several albums, especially if you ripped at lower rates like 64kBit/s.
I also recall exchanging MP3s on IRC with /dcc send, and am reasonably confident this was 1998 or earlier.
On the other hand, "On July 14, 1995, Karlheinz Brandenburg sent an e-mail announcing the .mp3 file extension had won a poll and announced that the old .bit file extension should no longer be used."
So while literally 1995 is early for people to have a "collection" MP3s on their home machines, the time before everyone had moved on _from_ Windows 95 sure overlapped with the mp3 era, especially for early adopters.