I've never tried Song Spy (I'll have to check it out,) but for mp3s I usually go with audiogalaxy (with the AGStreme interface.)

I don't know first hand about videos, but I hear Kazaa lite is good for those.

And there is always eDonkey to fall back on when you can't find what you're looking for anywhere else.