Photoshop will definitely be your best bet. But as far as the right solution, I think it really depends on image content. Rotating might not work.
In Photoshop CS5, they added a new feature called "Content Aware Scaling". This feature is awesome! In the Ps CS5 demo, Adobe showed a square image being stretched to fit a landscape layout (postcard). Everything stayed in proportion, simply amazing.
Definitely work a try.