Right now I'm working on doing streaming intermediate resizes that never load the full decompressed image into memory, because I need to be able to take uploads of 50 megapixel images and be able to respond with new versions based on user input in a timely manner. RMagick may be an extremely shitty implementation, but even a more solid one is stymied by the algorithm.
The solution is to just do something else -- for JPEGs, libjpeg has the capability to do a cheap streaming resize to 1/2, 1/4, or 1/8 by partially sampling the 8x8 DCT blocks and for PNGs MediaWiki's image server includes a utility for doing streaming resizes, though it's finicky about the exact scale factors it'll allow: http://svn.wikimedia.org/viewvc/mediawiki/trunk/pngds/