The four big factors for GIF sizes are
a) whether they have a lot of consistent pixels from frame to frame that don't have to be redrawn,
b) how many frames there are,
c) the image's dimensions and
d) how many colours are being used.
For a), when there's big parts of the image not moving at all, make sure that those parts stay the same throughout; so you could copy big chunks from frame to frame before saving to web, for example.
Saving to web incorporates a check whether a pixel changes from frame n to frame n+1, and if it doesn't, it makes the pixel in frame n+1 transparent.
For b), you can assign specific timings to frames. In Gimp, you write them into the layer title. So you can do a lot of magic with that. First and foremost though, when nothing's moving, then don't redraw.
For c), well, that's an obvious one. Make sure though that you resize the image as early as possible because the things you're doing in d) don't bode well with scaling.
For d), you could build a very reduced colour palette for the GIF because when you save to web, the GIF should be put into colour index mode. Photoshop should have some tool where you can say how many colours are supposed to be in that palette. Try reducing that colour until you hit the sweetspot at which the quality is okay and the number of colours is low.
The lower the number of colours, the more a) comes into effect.
As an example, when you do a grayscale Humphrey Bogart GIF at like 200x150 where Humphrey sits at the bar in a wide shot, turns his head and looks at the camera, then you reduce the colour space to like 8x gray, draw the whole bar in frame 1 and only redraw the stuff around Humphrey that's moving, then save to web.
There's a walkthrough here:
http://www.tested.com/news/how-to-make-your-own-cinemagraphs-a-new-take-on-gifs/2253/
It details how to efficiently make some parts of the image not change in Photoshop, so that you have full control over that aspect.
