One interesting thing about JPEG is that you can rotate an image with no quality loss. You don't need to convert each 8x8 square to pixels, rotate and convert back, instead you can transform them in the encoded form. So, rotating each 8x8 square is easy, and then rotating the image is just re-ordering the rotated squares.
That doesn't seem to apply to images that aren't multiples of 8 in size, does it?
Only if the image width/height is a multiple of 8. See: the manpage of jpegtran, especially the -p flag.
Slight nitpicking, but you can rotate in 90° increments without loss.
Indeed. Whenever I'm using an image browser/manager application that supports rotating images, I wonder if it's doing JPEG rotation properly (as you describe) or just flipping the dumb flag.