Oh, I've been using Linux for years and had no idea this was a problem on some distributions. I guess I've just accidentally skipped the ones dogmatic about non-free codecs.
Now Arch, in the past I've used Ubuntu and Gentoo. I may be misremembering, but I think in all of them there is a packages with non-free codecs either pulled in automatically or at least recommended when you install a media application.