Abre la imagen con GIMP, y vas a imagen->modo->indexado. Le dices que lo reduzca a 16 colores como máximo. Luego lo guardas, y ya está.