I've never understood the "MP3 support on Linux was terrible for a long time" thing--when was this long time? I'm pretty sure I was playing MP3 files under Redhat 6.2... how long ago was this?
My first experiences with MP3s on Linux was with RedHat 9 and Fedora Core 4 - Fedora 9. Yes, it was always possible to install the restricted codecs, but only recently were those instructions and processes made easier (and now, with recent distros, automatic). Maybe I was doing it wrong, but asking a user to install "restricted codecs" for something that Windows Media Player can do automatically isn't good for making users feel comfortable with your system.