(Some of these codecs are Windows
Some distros now aren't even shipping with MP3 support "out of the box". Sure, the encoder (lame) and decoders are GPL, but they still won't ship due to fear of being sued into oblivion.
The only way you are going to get a Linux desktop with everything like this working, is if you pay for it. I'd suggest Linspire or something. If you aren't going to pay for Linux, then you're going to pay for your time in setting it up.
It's sad, but thats why you pay a premium for Windows and Mac OS X, while I get Linux on Bittorrent (legally). I'm cool with it.
-- Free Software fan and Kubuntu Linux user.
Now back to your regularly scheduled Gnome vs. KDE flamefest. (You know its bound to happen.)