MP3 format is pretty lossy. It kinda sucks for quality if you're an audiophile.
Here's what I think is going down.
The primary mp3 codec used on linux is LAME (Lame Ain't an Mp3 Encoder), and has some optimizations that make playback quality a little bit better.
There was also a plugin for XMMS in the past that accomplished the same thing by post processing effects.
ETA:
I'll bet that if you install the LAME libraries on Windows and playback using the LAME codec, it will sound better.
Moar ETA:::::::
Check out ogg and flac.
To my untrained ear, ogg sounds better than mp3, but is a smaller file size. Flac is lossless, so you don't lose any quality at all, but it keeps the file size down a bit too. Of course if you guys have music players that don't support these formats, you won't be able to use them.