Hace unos días comentaba una nueva tecnología para redimensionar imágenes denominada Seam Carving, que afectando lo menos posible a la distorsión de la imagen. Ahora ya están disponibles algunas soluciones:
Liquied Rescale es un plugin para GIMP que ahora permite hacerlo.
Picutel Smart Resize v1.0 es un plugin para Photoshop (solo Windows, para Mac aún habrá que esperar al 2008).