You could:

• Try with a smaller image size. (ie:65x65pix)
• Also play with various types of GIF compression, like 128 dithered and stuff. (If you´re using ImageReady then this would be a breeze.