Según como sea la original, si tienes mucha resolución aún siendo pequeña puedes sacrificar resolución por tamaño y no se pixela. Pero si la resolución es de 72 ppp (pixel por pulgada) y no tienes mucho tamaño no hay nada que hacer, si el original es muy malo no hay nada que hacer etc...
Si tienes el photoshop te vas a ----imagen----tamaño de imagen, en esa pantalla te saldran varias opciones, y abajo te pone la resolución, si tienes una buena resolución (250, 300 ppp), desmarcas la opción ---remuestreal la imagen- y bajas la resolución a 200 o 150 ppp, con ello ahora tenemos mas opciones de tocar el tamaño en pixeles, y ya estaría. Pero no olvides que la imagen original tiene que tener un minimo de calidad y que no esté pixelada o reventada o saturada ya que en cuanto amplies se notara todo mucho mas y sin opción a arreglarla. Con lo que te he dicho ahora tienes que "jugar" tú con la imagen.
Si no lo tienes dame la imagen y miro lo que se puede hacer.