Do you mean fair as in FCFSFIFO, because that's the definition of fair? I think this would give you poor performance --> high response time and probably would also create problems with audio playback. The problem is that schedulers are always a compromise. For example CFQ has apparently good response times, which is generally very important for schedulers of any kind. Another scheduler you haven't mentioned yet is BFQ, which has worse response times than CFQ but a higher throughput, which can be less of a problem on desktop systems. You could try using BFQ, I have it on one system here, but I never had problems with IO really anyway.
I don't think this is much of a problem of Linux anyway. HDDs are just the slowest part of the computer and this is one other aspect of the von Neumann bottleneck. It would be interesting to know how much RAM you have on the affected systems. I tend to use much as it significantly improves interactivity.