If it's a JPEG, try adjusting the compression factor. It may create more artifacts, but you might be able to get it down in size. If it's GIF, try reducing the size of the image and the number of colors.
For PNG, yes, OptiPNG should work very well for full-color images. Using it on the default settings usually gives pretty good results. If it's alpha-channel, though, it may be pretty big. Try removing the alpha-channel so that it's single-color transparency (this may require image editing experience). If that's not enough, PNG has a 256-color mode that compresses better than GIF does at the same color depth.
Oh, and by the way, _please_ don't use MSPaint to save pictures. JPEG and GIF images turn out looking terrible and PNGs are hardly compressed at all. Use other tools to save as different formats. I hear IrfanView is pretty good.