1. This uses the Image Magick command "convert" so it will work on any system that has it installed. I've only used it on Mac and Linux.

2. It isn't lossless, no. I think jpegtran can do this, but you'll need to first read the correct orientation out of the EXIF data and then give the right arguments to jpegtran. Since the loss in quality is tiny, I just use -auto-orient.