Hmm. Lots of issues here, welcome to the wonderful world of web graphics.
It's not easy to find out what the most common screen setting is. The two most common are 800x600 and 1024x768. Very few people -- if any -- use 640x420 (or whatever it was) these days. But quite a few have screen resolutions set higher: these are probably graphic designers and/or people with huge monitor screens -- but they often don't maximize their browser windows anyway (especially if they're using Macs).
An 80k image is huge. As a rule of thumb, you want the whole page -- code, text, stylesheets, images, everything -- to be not more than about 100k, more like 50k or 60k if you can manage it, unless you are fortunate enough to be developing an intranet site or a kiosk application. But your question about why the JPEG is smaller than the GIF throws up a whole load of issues.
It's not so much the number of colours that make the difference. It depends on how you save the image. Of course, if you have a gradient from, say, red to pink, you might intuitively think you have two colours (red and pink), but there could in fact be dozens.
You can take any GIF, convert it to a JPEG and then compress it to a size smaller than the original. This will work best if there are no hard contrasts anywhere. But this will usually involve overcompression.
Look carefully at your JPEG, paying special attention to areas of flat colour and sharp edges in the image. If you see a blotchy, speckly effect, or colours bleeding, you have overcompressed the image. JPEG compression works by throwing out information it thinks you won't notice, so you have a choice between high quality large files and low quality small files. JPEG isn't good for flat colour hard edges type images (e.g. cartoons) because the "JPEG artefacts" are noticeable and can make the image look really ugly.
Also, look at the GIF. It could be that it is "dithered". "Dithering" is when a colour is approximated by mixing pixels of different colours: e.g., orange can be approximated by using a pattern of red and yellow pixels. This is sometimes useful, but will often increase the size of the GIF file. When you convert a graphic to GIF format, make sure any "dithering" option is turned off.