No sé en Photoshop, pero en Paint Shop Pro cuando cambias el tamaño de una imagen puedes elegir varias opciones: Cambiar proporcionalmente pixel a pixel, bilinear, bicúbico, etc. Yo he ampliado muchas imagenes 4, 5, 6 veces y en modo bicúbico el resultado es MUY BUENO (Siempre que la imagen original no sea una porkería en si, claro
).
De todas formas vigila dos cosas: No comprimas demasiado los JPG, y si no tienes mucho problema de espacio, intenta guardar como TIF, la calidad es mejor. Normalmente no lo uso pero he visto por ahí que el PNG tambien esta bien...