What image format you should use just depnds on the image.
gifs can be a maximum of 256 colors. Starcraft runs in 256 colors, so there's no color loss, but if you have a photograph it might not look so great as a gif. Also, gif is the only normal image format that can be animated with multiple frames.
Jpgs are in 24 bit color (16.7 million colors) and have an adjustable compression factor, which can be anywhere from 1-99. The higher the number, the worse the quality of the saved image. There are some techniques to diminish jpg artifacts but for the most part the damage is un-undoable.
Pngs have more flexibility than jpgs. They can have any size pallete and alpha channel or single color transparency. The size of a png depends largely on the size of the color palette, so it's good to reduce it as far as possible without losing quality.
Here's an example of what jpg compression can do to an image, along with a comparison of what sort of file sized you get from using different formats:
_Jpg compression at 1_

_Jpg compression at 50_

_Jpg compression at 99_

The maximum-cmpressed jpg is the smallest, but as you can see the image is totally ruined.
PS.
Yeah, I know it's completely off-topic. =P