Cool picture, Chris. There was a tutorial I once saw on how to straighten out crooked scans but I didn't bookmark it. If you ask this question in one of the photoshop groups you'll get an answer very quickly. However, there's a pretty easy way to fix this horizon and not lose anything. Duplicate the layer, then bring up the transformation box and tilt the whole layer to the left to straighten the horizon. Apply the transformation (double click inside the box).
Next, put a layer mask on this layer, and while using the default colours of black and white, paint part of this layer away with your airbrush at low opacity with black colour active, and/or back in again with white until you have something you like. If you aren't familiar with layer masks you can use the eraser, although this isn't as forgiving.
Layer masks are overlooked in photoshop and well worth the time to learn. You can probably do a search and find dozens of sites with tutorials on how to use layer masks.