Using a lossy compression format like JPEG, you can crunch the file size down to just about anything reasonable. Most image viewers/editors allow you to specify a "quality" setting for JPEG's which allows you to trade off file size for quality. Do a few quick tests, you may be surprised how much you can shrink the file sizes without noticeably hurting image quality.
I highly recommend
IrfanView, which is a very versatile (vast image format support), fast, and allows you to perform batch conversions with user-specified criteria. It is mostly a viewer with a basic editing abilities and filters. It won't replace PaintShop Pro or PhotoShop for power users, but for example, I prefer to use it for all of my general image tasks because it is so fast and stable...importing (scanning), cropping, directory thumbnail viewing, negatives, resizing/resampling, rotating, etc. And best of all, it's free.
Best regards,
Floyd