I found lots of discussion, and many proposed solutions, and patches to this problem. It seems that many (mozilla, poppler, others?) using cairo (or pixman) is maintaing some patch that fixes the ugly downscaling output.
Related information for reference:
Created attachment 78522 [details] [review]
Pixman now implements convolutions, so this bug should be rather easy to fix. Here is an example patch.
This patch has landed in trunk, and will be part of the next release.
The patch had to be reverted.
Another patch has been proposed and is under consideration:
The aforementioned patch has landed; please re-test and share feedback here or on the mailing list.
I'm going to close this bug as fixed, assuming the new downscaling patch does the trick. If it does not, or if there are any concerns, please reopen this patch so further investigation can be done.