I would create two versions of this GIF, one at 600x800 and one at 1200x1600 (edit -- or appropriate for your image -- these would be maximums). You'll need to code two <img> tags, one for each, and assign them unique id= attributes, e.g.
The default is to display the smaller version of the image. Devices that don't support media queries will always show the smaller one. KindleGen will use the smaller image in the package it generates for the older Mobi 7 Kindles and use both images in the one it generates for the KF8 Kindles, which support runtime media queries.