El tema con el GIF es la cantidad que se maneja de bits. Las imágenes como el JPG y PNG manejan hasta 32 bits de colores, los cuales son MUCHISIMOS, 16.777.216 (16.7 millones). Mientras que el gif maneja hasta 256 colores, no bits, sino cantidad de colores. Lo que sucede que para el degradado se utilizan muchos colores porque cada pixel tiene una diferencia mínima del color con el otro y al tener menor gama de color lo que sucede es que el gif se ve mal.
El gif no fue creado para imágenes de alta calidad, por el contrario para cosas de menor color, mas livianas y animadas. No está hecho para utilizar fotos con demasiados colores, aunque ahora con los 256 se ven "bastante" bien las cosas. Fijate Photoshop te da la opción de la cantidad de colores que quieres usar en el gif.
Cuándo colocas la opción:
GUARDAR PARA WEB Y DISPOSITIVOS te aparecerá la opción del gif y la
CANTIDAD DE COLORES