Open your gif with the gimp, and use the menus to go to Filters > Animation > Optimize (for GIF)

It'll think for a moment. when it's finished, use the menus again to go to Image > Mode > Indexed...

The Indexed Color Conversion dialog opens. In this window, you have a number of options. The best looking will be the first option, Generate Optimum Palette (255). This will also have the largest size however. Below, I've shown some of the options, along with the final file size for you to compare with.

Original GIF - 1638.4KB	"Custom Web Palette" - 998.33KB
Generating a custom palette - 795.61KB	Custom palette 50ish colors - 480.59KB

Pick whichever choice you think will give you the best results, and click Convert.

Last step is to export your image. GIMP 2.7 and above don't use the save dialog box anymore, and have a special export menu under file. This can also be accessed using CTRL+SHIFT+E.

As you can see above, the final image for me was roughly 1/3 size of the starting image, and it looks the same, or good enough for a GIF at least.