Non dipende dallo sfondo allora, ma dall'immagine 'visibile'.
Gif supporta pochi colori, se crei l'img usandone molti, in fase di riduzione resta una fila di pixel intermedi che non diventano trasperenti, perchè ne puoi avere uno solo trasparente.
O crei partendo da pochi colori, e cercando di disegnare un bordo uniforme e netto, o quando esporti in gif cerca di impostare una tolleranza alta al colore trasparente.
Cmq con le gif per esempio tratte da foto, l'unica è colorare a mano i px 'di mezzo': ingrandisci l'img, seleziona il colore di fondo e coprili con quello con il pennello.
Oppure, se è un bordo continuo, selezionalo con la bacchetta magica (se tieni premuto shift puoi selezionare anche aree adiacenti ma separate) e poi riempi la selezione con il colore che vuoi tendere trasparente.