I've been evaluating some software for a client to resize pics without losing detail, and find that Genuine Fractals
6.0 ($160), PhotoZoom Pro
2 ($240), and Image Enlarger
0.8 ($0) do an
amazing job of producing sharp, clear enlargements, as can be seen in this comparison of a 64x64 sample enlarged to 256x256 (4x):

For rescaling high-contrast images by 2, 3, & 4 times, however, there is simply no better algorithm than
HQx (
Code page)

If you want 'content aware' rescaling, but don't want to pay the big bucks for Photoshop, the generic term is '
seam carving' (software links at the bottom of the page). You can resize scenes like this

or even remove portions of a scene, like this:
