Tritt das auch dann auf, wenn du dir solch eine Grafik mal direkt ansiehst (Kontextmenü), ohne dass sie innerhalb einer Webseite dargestellt wird. Ich habe den gewissen Verdacht, dass Firefox da aus irgendwelchen Gründen eine recht geringe Skalierung vornimmt, die dann ohne aufwändige Interpolation zu solchen Effekten führt.
Einen transparenten Proxy, der Bilddateien komprimiert nutzt du nicht zufällig (unbewusst)? Zumindest ein deutscher Mobilfunkanbieter macht das nämlich ungefragt. Allerdings sollten die Bilder dann eigentlich anders kaputt aussehen.
