I've been happy with MP3's. They sound good enough most of the time (as long as they have a decent bitrate), they play everywhere, and they have a small file size. The lossless formats sound great but I don't think it's for it for me due to the file size. I usually listen to music in a noisy environment (noisy home office with kids and computers, airplane, driving) and the additional sound quality is wasted.
I listen to most of my music through a shoutcast server I run so everything is downsampled to the broadcast bitrate of 128kb/s 44khz. You can listen too at http://www.x-j-nine.com:8000
. Just click on the "Listen" link at the top of the page. It should play through Winamp and iTunes and maybe a few other players.