It was either that or MP3Sparks.com, I think. But it wasn't long before I discovered torrents.

MP3.com [1] founded by Michael Robinson (of Lindows/Linspire fame).

[1] https://en.wikipedia.org/wiki/MP3.com#History

Oh wow that takes me back haha!

I used to use mp3search.ru (project closed now). Tracks were like $0.10.

There's a name that takes me back.