You should use jpg for the thumbs (save them at a medium/low quality) and gif for the slices with text or flat colors (reduce the number of colors as much as you can, to get a smaller file size), then of course gif for the animated slices. I asume your slicing them in Adobe Image Ready, so you can use different output settings for each slice.
Good luck!
