Umm.... Lt_Major_Burns, I THINK you may be wrong about the "part of the image is the same" thing.... I remember taking apart images using "GIFbuilder" (Which is the program I'd recommend, by the way, to make animated gifs), and I remember seeing that some frames only contained what changed from one frame to the next.... like a banner, where most of it was static, and then a small animation existed....
But, yeah... GIFbuilder is what you're looking for. It's a little long in the tooth now, and slightly clumsy, but does a great job, anyway.