I can't help you with using photoshop specifically as I don't use it (I tried v4 & v6 ages ago, and found them to be very bloated & a royal pain in the ass to use), but for gif optimizing in general....
The only ways to reduce the size of an animated gif without affecting quality are collapsing frames, making redundant pixels transparent, and a new one I just learned of "dirty rectangle". I've seen the dirty rectangle effect before but had always attributed it to transparent pixels. Instead, dirty rectangles actually delete the unchanging portions of the frame, then place the smaller image in the correct location.
The only other ways to reduce filesize in a gif all involve reducing the quality. You can remove not-identical frames (can often be done without too much impact on visual quality, but can result in a very choppy animation). {I believe this is what you did manually. The auomated frame removal process only removes absolutely identical frames, but many frames are identical to the human eye without being absolutely identical, and thus get left alone by the automated process.} You can crop or resize the image to smaller dimensions. You can reduce colors.
The only other thing you can do (in some programs, but not all) to reduce filesize is move colors from a local palette to a global one. This may or may not reduce the filesize (depending on the specific image) and may or may not impact quality (again, depends on the image). Each frame in an animated gif is capable of having it's own palette of up to 256 colors, a fact which allows you to have an animated gif with more than the 256 colors that gifs are normally limited to (as illustrated in a fairly well known "hack", where a true color gif was produced by layering many frames with local palettes over each other & allowing the other frames to show through via transparency). While these local palettes can improve the visual quality of the image, they also bloat up the filesize.
Here's a tutorial that might help you a bit:
GIF Movie Gear: Support: Tutorial (The tute is for a different program, but the principals are the same no matter what prog you use.)
