Если не хочешь жертвовать качеством картинки, то GIF не подходит совершенно. В GIF крайне неудобно работать более чем с 256 цветами и практически невозможно найти редактор, который это вообще умеет делать. Причём из-за ограничения в скорости отрисовки анимации gif-изображений в браузерах блоки в анимации будут рисоваться по-одному, а не весь кадр сразу (http://phil.ipal.org/tc217.gif — вот как-то так, паузы между кадрами должны быть 0ms, но браузер не позволяет этого).

Можно было бы APNG, но он практически нигде не работает кроме Фокса. Даже в Хроме.

А то, что я видел, было именно каринкой с одним целым опорным кадром и кучей мелких блоков с diff-ами, которые нужно накладывать. В отдельном файле шёл JSON с номерами кадров и координатами блоков которые нужно взять из текстуры и куда их прорисовать.

Хотя конкретно в их случае можно было бы и попробовать уложиться в GIF-ку. Если каждому кадру давать свою палитру, то сработало бы — у них цветов мало совсем, но мне не известен графический редактор, который умел бы и gif-анимацию, и отдельную палитру каждому кадру давать. Все, что мне известны, умеют в gif выводить только если индексировать все кадры одной палитрой.