Have you heard of Seam Carving before? Seam Carving allows you to stretch or squish images without distorting them. It's an amazing process that you have to see to believe. The video is just a little over 4 minutes and well worth it (even my wife thought it was cool, though she might have just been pretending).
I learned of this through a blog post by Mike Swanson. He has created a .Net version of this algorithm. I'm really hoping that this makes its way into Paint.Net!
For more details about Seam Carving, check out Seam carving for content-aware image resizing [20 MB PDF].