Let me introduce you to the Liquid Rescale plugin. It magically knows which rows/columns should be removed. It's not perfect, but the results are sometimes impressive nevertheless.
Here's your image liquid rescaled. Keep in mind that the only parameters were the target dimensions.
This photo resized to widescreen. Again, the algorithm decides what to remove on its own, I've only changed the image height:
Now the coolest part: the same photo, but with the dog automatically removed by Liquid Rescale. I just had to paint a "feature discard" mask over the dog. The algorithm decided what pixels to put in its place.
This is what the feature discard mask looked like: