Animated GIF banner - which compression?

I created an animated banner for a client and per there specifications, it needs to be around 50kb - 100kb :run: (Also they said the quality cannot reveal banding/dithering)

Right now I used imageready - to produce a large 400kb animated gif.

I tried several settings:
Gif 128 dither/no dither - 400kb/300kb
Gif 256 lossless - 450kb
Gif 64 dither/nodither - 240kb

The project was simply to convert a premade banner from flash to GIF, because the exported GIF from flash was 2mb

Does anyone have any tips on compressing an animated GIF with the correct settings in order to create a clean image, with small file size?

Any help appreciated, thanks.