В любом приличном растровом редакторе(фотошоп, гимп) или специализированном по для гифое(см. тред в /gf/). Автоматически, функции вроде "Оптимизировать для gif".
Да, кроме того места, где что-то шевелится, там кусок будет перерисовываться после движения. Это кстати, будет "Фон".

Тебе бы озаботится следом, который оставляет нога человека на пустом пространстве.