The best thing to try is lowering the number of colors. I bet with 64 you can hardly notice a difference.

Edit: I tried it at 32 colors (no difference I can tell) and its 105kb. At 16 colors (a little difference) it was 75kb.