The user should know better than doing "make -j10" while trying to watch video, unless they have an 11-core CPU.
The problem isn't that the scheduler allocates time fairly; the problem is that the operating system sets all 10 children of make and the video player to the same priority. This is not a sane default. The Operating System should have an idea how much priority an application needs, and an end-user who doesn't know about .bashrc files shouldn't have to think about it. Make and its children should be reniced to 15 (for example) and totem should be reniced to -15 (for example) without any user intervention. Audio and video applications should have high priorities; Firefox, Thunderbird, Solitaire and OpenOffice should have medium priorities; video encoding and compilation should have low priorities by default.
If assigning arbitrary numbers to applications by category so they sort themselves out correctly seems crazy, remember that System V init has been doing it for years: every init script has a 2-digit number, and those numbers determine the order in which scripts are run.
A quick look at top on my system (Ubuntu 10.10) shows only 4 tasks with priorities != 1, and only 2 tasks with nice values != 0. Nice values and priorities are a simple tool that can solve these problems (assuming desktop preemption) so why aren't we using them? Cgroups are a great tool (killer feature!) but it seems like swatting a mosquito with a laser-guided rocket-propelled grenade launcher.
(Someday I want to try swatting a mosquito with a laser-guided rocket-propelled grenade launcher.)