Seria bueno saber que programa de retoque utilizas, para que te aconseje alguien que utilice el mismo que tú.
Yo te cuento lo que hago con el photoshop, la versión CS, primero ajusto los niveles, si necesita saturar, mascara de enfoque y luego por ultimo, voy a archivo Guardar para web y ahí es donde le digo el tamaño que quiero y lo que quiero que ocupe, por ejemplo, aquí el máximo permitido para una imagen es de 150 Kb, yo suelo ajustar a 145, para que con la información del servidor no exceda ese peso.
Todas las imagenes pierden calidad al variar su tamaño, pero no deberia notarse mucho, cuando se trata de reducir, no así con la ampliación.
Espero haberte servido de ayuda.