Edit: According to the bug report linked in the comments, the problem is a little more subtle. On Linux, Firefox uses a library called Cairo for image rendering, including rescaling of images. Cairo can either let graphics cards do the heavy lifting, or it can do it in software on the CPU as a fallback.
The problem is that many Linux graphics drivers do not correctly declare their capabilities, so Cairo has no idea whether or not it can offload particular types of processing (like image rescaling) to the GPU or not. So the fix is to always use the software fallback for image scaling, even when the graphics driver could do it in hardware. The FF developers decided that this was unacceptably slow and disabled it, leaving Linux users with ugly rescaling instead.
The bug report also links to a PPA that has a patched version of Cairo that uses the hardware rendering path. Presumably this will break if you have one of the offending video cards whose driver says it can to rescaling but really can't, but will work if you have a driver that behaves.
(Original answer below)
I believe that the responsibility for smooth scaling on Linux falls to the X server, which doesn't support it yet. So Firefox 3 and up knows how to tell the OS to do smooth scaling, but not every OS knows how to do it yet.
Maybe in 9.10 Karmic.