you're right about gifs using the LZW compression schema. It's pretty garbage for images, even with such a low cap on the color palette. For animations it just LZW encodes each frame and stores them sequentially in the file, bracketed with some descriptive metadata. The main space savers are using a global color palette, reducing the palette size by half so that the code table can use fewer bits, and using transparency for pixels that don't change color from the previous frame, which, depending on the image, may not even do anything on its own. Also if the change in a subsequent frame happens entirely within some rectangular portion of the image you only need to encode the color info for that group of pixels, but that probably won't ever apply to your stuff, assuming photoshop even looks for that at all.
If you really want to get the filesize down you have to start shedding information even beyond what you're already doing by reducing the frame size and color palette. The main ways to do this are letting photoshop set pixels on subsequent frames to transparent when aren't exactly the same color values as long as they're still pretty close; and by using lossy LZW compression which encodes pixel groups the same way as similar but not equivalent groups that have already been put in the dictionary as long as they're similar enough. Both of those are broad-strokes, global things to do and results will vary widely depending on image content and how much leeway you give the algorithms.
If you want to maximize quality:file size then you're going to have to get elbow-deep in each image and do something to reduce noise in solid-shaded areas in a given frame, and inter-frame noise that happens when pixels that should stay the same change color. Or do things like blur out background details when all the action is up front.
If you really want to get the filesize down you have to start shedding information even beyond what you're already doing by reducing the frame size and color palette. The main ways to do this are letting photoshop set pixels on subsequent frames to transparent when aren't exactly the same color values as long as they're still pretty close; and by using lossy LZW compression which encodes pixel groups the same way as similar but not equivalent groups that have already been put in the dictionary as long as they're similar enough. Both of those are broad-strokes, global things to do and results will vary widely depending on image content and how much leeway you give the algorithms.
If you want to maximize quality:file size then you're going to have to get elbow-deep in each image and do something to reduce noise in solid-shaded areas in a given frame, and inter-frame noise that happens when pixels that should stay the same change color. Or do things like blur out background details when all the action is up front.