The main thing is colors. The original is at 256 colors and that's just not necessary for something that small. I took it down to 64 and there isn't really any appreciable difference.
I used a combination of
SuperGIF and ImageReady. Run it through supergif until it won't reduce anymore and that alone will more than cut the size in half, then use ImageReady optimization tools to further tweak colors, dithering, lossy, etc... until it's at the size you want.