Fewer colors means less information for each pixel,
thus a smaller file. If you can work in sixteen colors,
your files will be tiny and reproduce well on almost any
monitor. In no case should you use more than 256 colors
without a very good reason.
In the case of photographs, you can often reduce a
full-color image to 256 colors with little or no noticeable
degradation and a large reduction in file size. Just
reduce from full-color to 256-color, then right back to
full color, then save as JPEG.
Both GIF and JPEG files use compression, and a large
area of one color will compress much more than the same
area with a lot of detail. Photographs with lots of plants
in them will be bigger than ones with simple backgrounds,
for instance.
Generally, the GIF format works best for
computer-originated images, and JPEG best for photographs.
But don't be afraid to experiment.
Contrary to what you'd think, it's harder to reproduce
monochrome then color. Anything you can do to reduce the
number of shades of gray will help.
You'll almost always get better results
if the image contains some color, even false color.