How to decrease the size of animations by changing the source images?

[MobileVisuals]

I am making animated wallpapers for one of my customers MediaPlazza. They want animated wallpapers according to their specifications. I need to reduce the size of the animations to fullfill some of their demands for filesize and dimension. I only need to decrease the file size with some %. I am working with Jasc Paint Shop Pro, but whatever I do to adjust the source images, like add blur, the file size of the animation doesn't become smaller.

I have converted the JPG-source images to gifs and reduced the color depth to only 16 colors, but the gif-animation still doesn't get smaller. What can I do with the source images to get a smaller gif-animation?