Yes, I haven't done it and some C or python programming is involved, but I'm going to try soon.
My situation is a camera mounted on a mast which is on a a buoy taking a picture which always contains the horizon. This should be a simpler application than yours.
First, look in to OpenCV. Specifically the Hough Line Transform.
For my case, I expect that the horizon will be so much more distinctive than any other line, I can tune it to only find one line. I can then rotate based upon the line's angle.
For your application, I think you would filter out any line's more than X degrees out of horizontal or vertical.
A little statistics, and you may be able to figure out how much to rotate.
As to degraded image quality, I'll be converting RAW files to ppm instead of jpeg, so there shouldn't be much beyond some cropping.