Rsizr

Rsizr is a powerful online photo editing tool. It uses a technique called seam carving to resize images with little distortion. It does this by removing the least important pixels. The video by the creators can explain it better.

I tried it out with at rsizr.com. I used the preserve tool on the people in the image:

It didn't work too good in Firefox so I tried it in IE. The interface also isn't that great. I would prefer a standalone version and apparently you can download it as a plugin for Photoshop, but I haven't tried the plugin t yet.