Yo te recomiendo que Utilizes Illustrator ya que este achica las imágenes Manteniendo las proporciones, Aunque photoshop también tiene esta opción, Da medidas preestablecidas y queda feo, pero si tienes photoshop convierte la imagen a indexada pone 15 colores le das seleccion rectangular/ Forma libre y lo vas achicando Pero nunca cambies del modo indexado

Espero Haberte Ayudado

p.d Antes de hacer esto crea un nuevo documento con las medidas 64 X 64

SuerT