Un gif tiene 2 desventajas para este tipo de cosas "fusionarlos" con el fondo, primero la paleta limitada, pero lo segundo es que el color transparente solamente es un color liso.
Esos puntitos que ves son el alisado, esto es el "degradado" que es necesario para suavizar un borde inclinado en un mapa de bits.
Como el gif solamente recorta un color, todos esos colores intermedios saltan a la vista
La solución puede ser
1) Prepara desde antes tu trabajo para que tenga un color parecido al que vas a tener de fondo, y esos colores no salten tanto a la vista
2) Utiliza el formato png que ya te recomendó Manie que usa transparencia de otra manera, con un canal alpha, que este se funde perfectamente. (No compatible con navegadores viejos).
