Hola Ramon, la mayoria de imagenes que he visto pesan 9,8kb y algunas en PNG, el GIF siempre siempre he pensado que pesa mas que un JPG.
Hay algo que debes entender.
GIF guarda la información por bandas mientras que JPG lo hace punto a punto.
Si tengo una imagen con 3 líneas amarillas, GIF sólo guarda información de cada línea (claro esto es más complejo pero es para que me entiendas), mientras que JPG guardará información para el píxel 1, para el píxel 2, para el píxel 3, para el píxel 4... así hasta completar la imagen. En una imagen de 32x32, JPG estaría guardando 1024 datos, mientras que GIF, si sólo hay 3 colores sólo estará guardando información de 3 datos. Imagínate el ahorro.
Si tengo tiempo armo un tutorial para que se entienda mejor este problema y qué formato escoger en cada caso.