OK, so I discovered image magick was NOT set in my config.php - I forgot I had since reset a lot of settings. I set it, and that fixed things. For purposes of comparisons, here are three comparisons:
Image Magick switched OFF (GD I guess doing the resize):
#removed_broken_linkImage Magick switched ON WITH -interpolate bicubic:
#removed_broken_linkImage Magick switched ON using default settings (no -interpolate):
#removed_broken_linkAs you can see, Image Magick is a HUGE improvement, not just in the jaggedyness but in the colours as well. It's debateable though whether adding -interpolate really adds any quality. It might be nice though to have more of image magick's command line options available in config.php. And definitely I would tell your users to install Image Magick for overall quality if they can!