Prueba en formato .PNG y con el perfil de color en sRGB. Es el formato y el perfil que yo uso para Facebook y Flickr.
Los archivos .PNG soportan mejor que los .jpg la re-compresión de los servidores gratuitos de Facebook, Flickr, Instagram, etc.
No es que re-compriman por ser mala gente, lo hacen para no tener que cobrar por usar sus páginas y para bajar el coste de servidores de terceros que se contratan para almacenar tantas imágenes.
Marcadores