This depends much more on the type of icon you're talking about, and how they were made, than on any Windows/Linux difference.
If you look at a small bitmap-type image that was upscaled to a larger resolution, the result will look bad - a good scaling algorithm will help, but it won't ever be perfect for non-trivial images.
A lot of icons (on Linux) are still shipped as PNG images (or other raster formats). They'll look good if:
- they are displayed in the appropriate resolution
- their creator put a lot of effort into them to make them look clean (duh!, but that's important, and it requires some talent)
(Windows ships its icons in various sizes so that it pretty much never has to scale them - the artists that produce them can "hand tune" each resolution to make it look good. Some Linux icon themes do the same thing, with similar effect.)
For vector graphics (like SVG), the scaling problem doesn't exist as long as you have a good rendering engine. Linux has perfectly good SVG renderers these days. So the only thing needed for this type of icon from looking good on Linux are good artists and support for vector graphics in applications/desktop environments.
I'm not familiar with fluxbox at all, but KDE uses (or can use) SVGs for icons. For instance, check out the Crystal SVG theme's screenshots - nothing blocky or aliased about them. Look for recent KDE screenshots with similar themes, and you'll see you can get rather high-quality graphics/icons on modern Linux desktops.
In short: it's not a matter of Linux graphics engines being less advanced (generally) than Windows ones. It's more a matter of time invested in "making stuff pretty". Graphics (and UI design in general) is very time consuming. Creating all the necessary icons is time consuming.
There's also the matter of some environments aiming for raw speed/low overhead over eye candy - the overall appearance isn't as polished as other desktops not because it's not doable, but because it is not desired to make that "performance" tradeoff.