Are your images properly sized? If you displaying them on your webpage as 300x300 pixels make sure the original image is the same size.
This helps two-fold, one its less data to download, and 2 it doesn't require extra processing power for the browser to resize. Additionally, the image will look crisper if its the exact size.
As far as the difference between GIF and JPG, (with the exception of transparency, which JPG doesn't support), it boils down to what your image contains. GIF uses a color table and a map to that color table to store the image, while JPG uses a compression algorith. So, if you image contains few color variation you will get a smaller filesize from a GIF. Conversly, if you have a photograph with lots of color variation you'll want to use a JPG.