The theory is that you have the image off the sensor, and then you have metadata about the image in the EXIF fields. The debatable point is whether orientation should be treated as metadata or is inherent to the image data. On early digital cameras, this wasn't so debatable since adding an orientation sensor was a deluxe feature that really did just add another bit of data to the photo.
I was assuming the rotation tag only expressed axis-aligned rotation, in which case lossless rotation is not that expensive compared to taking the photo in the first place.
Why should it rotate, when it can use the standard method for notating the proper rotation? Your camera would be a lot slower if it had to rotate 16MP images between snaps.
I suppose the device wouldn't bother with lossless rotation when displaying on the screen. When it comes to saving the image, it has to be lossless, which would probably take a lot more computation power.
Somebody covered this further up, but in more detail:
It is not the rotation itself that is the problem, but saving the resultant file. If you're working directly with the pixel buffer you only do a lossless JPG rotation if the image height and width are multiples of 8 (or 16, in some situations). This is because once you've performed the rotation you'll need to save the resulting output as a JPG, and unless your dimensions factor into the block size you'll need to recompute. This SO answer covers it in more detail[1].
However, if you're not working with the pixel buffer this doesn't apply. You can use jpegtran (part of libjpeg), for example, which manipulates the JPG file directly and never decodes it. Many basic image viewers and editors (like the Windows Picture Viewer, and probably the iOS Photos app but I'm not sure) don't use this approach though.
Because JPEG files don't store a value for every pixel in the image: the information is encoded very differently. By good fortune, lossless 90 and 180 degree rotations are possible for the JPEG format, but only for certain image dimensions (multiples of 8 or maybe 16, as I understand it). Some notes on what is possible can be found at http://jpegclub.org/ .
I've been looking around to see if ImageMagick could do rotation without degrading quality. (I'd also asked a question about that elsewhere in this thread.) So I assumed that most devices use something similar even for displaying on the screen. It appears I assumed wrong. :)
I saw your other comment about axis-aligned rotation not being too computationally expensive. In that case, why aren't iPhones doing it by default? Wouldn't their computation power be comparable to that of most of the cameras that rotate the images? Or are cameras better equipped to handle such transformations?
Other cameras don't usually rotate the photos (I've had to fix this same bug myself before the iPhone existed). My guess is that they didn't notice it earlier because photos from cameras are more likely to go through some post processing that on the final export saves the image with the data already rotated.
By decoding the jpeg, rotating the pixels and saving the jpeg again. I'm not even sure it makes sense to talk about lossy and losses when displaying images.
But when browsing through already stored pictures, a bit of delay is totally ok. Not so much when quickly showing some information overlaid over the picture you've just taken.