Using Photoshop the warp tool is a pretty good option here, use the select tool to select the right side of the image and going just past to the left of the sun. CMND+J will take this selection onto a new layer then CMND+T to enter transform mode, right click and select "Warp". Drag a guide down so you have a level line to work off and start with the top two warp points on the right, move these down a bit and you'll also want to move the left side top warp point up a bit.
After a bit of tweaking around with this you should be able to get a straight horizon, but the right side of your image would will have shrunken somewhat due to the warp transform. Create a mask for this layer and paint it out just above the old horizon then choose a way to paint it out through the foreground, use a softer brush for the horizon and a slightly harder and smaller brush for the foreground.
You'll also want to blend the layer in from the left hand side to the original using the mask, so keep this in mind when you're doing the warp so your original and new horizon line have a meeting point that leaves you with a straight line.
