Primero, si transformas de JPEG a GIF perderas colores. GIF permite 256 colores como maximo, mientras en JPEG puedes utilizar millones de colores. Necesitas reducir el color en tu imagen, si es una fotografia se notara mucho la diferencia.

Una buena eleccion del metodo por el cual se reduciran los colores te puede ayudar, Floyd-Stenberg es bueno, pero trata los diversos metodos que tiene el software de edicion de imagenes que estes utilices ya que a veces el resultado depende de la imagen y los colores que esta tenga, algunos metodos trabajan mejor con determinadas escenas .

Puedes tratar con GIMP, photoshop o paint shop pro (busca en el el modo de imagen y cambia de RGB a indexado, en paint shop pro, busca "decrease color depth").