- reduce the image size (fewer pixels = smaller file)
- reduce the frames in the animation
- reduce the color pallet further
- posterize the images (larger flatter areas of color compress better for GIFs)
- Use software that can add additional compression techniques (IIRC, Fireworks is good for this)
Reducing image size and number of frames will be most effective by far.
GIF can encode only difference between frames, so you can also try to reduce size of the area of the image that changes, i.e. have as much unchanged/non-moving background as you can (pixels must remain completely identical between frames, even slight temporal noise will still take space in the file).