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.