Not sure about MusicMatch, I'm not that fancy in the playlist department, I just use XMMS (Winamp clone ... ish)
For MSN compatibility there's Kopete and Gaim (both support other protocols as well, yahoo, ICQ, etc.) Bear in mind, though, that they're not quite as fancy as the M$ client with regards to the emoticons and stuff, but the basic functionality is in place.
P2P ... hmm, I don't know of any Kazaa clones, I'm more partial to the donkey network. For that there's xmule, which is an emule clone, and some people use mldonkey, not sure what that is, though, as i've never used it myself.
--edit--
Ah, Floid beat me to it.
Oh well, that's what I get for doing all sorts of other stuff while replying, I guess.
