Me han recomendado optimizar los recursos de formato GIF, alguna recomendación que no implique que luzca pixelado o con “manchas” como si...

Normalmente en tu pagina no deberias usar gif, para logos usar svg, para fotos jpg,

Depende mucho del tipo de gráfico que estés presentando, quizá puedas cargarlo como SVG sin ningún pixel y con la capacidad de insertarlo en cualquier tamaño ya que son vectores.

Si es una gráfico que no pueda presentarse en vectores entonces podrías intentar en JPG, para web se acostumbra que sea a 72 DPI y 8 bits de color, en programas de diseño como photoshop puedes ir probando la calidad de la imagen e ir bajando, entre mas bajes la calidad mayor sera la compresión de dicha imagen.