But then they would need a new domain.
Not really. gfycat does both gifs and webm.
It would also be more efficient to be able to tell when the gif started
Changing the desktop background to a solid color would help too.
Doesn't GIF's difference encoding mostly make the background a constant cost?
It would make the initial frame smaller, but the difference on following frames should be negligible yes.
The only disadvantage visible is Internet Explorer users who don't have the plugin installed, in which case you could provide a gif fallback.