The file format is dependant on what use it gets, the size and quality is based on compression as well as being what makes it different. For pictures, it's hard to beat .JPG as long as the quality is maxed you'll see no difference between .JPG .BMP and .TIFF, and it's smaller than either. Some programs just use different formats, and depending on what is actually in the file, a different format could be smaller with higher quality, or larger size with lower quality.
Generally on the web .JPG and .GIF, both are smaller than .BMP and with animation and transparency options from .GIF it's often something of a neccesity. Depending on the image .JPG or .GIF could be better because of the way they compress, .JPG groups pixels together to compress but has millions of colors in its pallete, .GIF removes colors from the pallete, but only has 256 max. As a general note, use .JPG for pictures in web, use .GIF for solid and block colors that don't have a lot of variations or continuous tone to it, images that need transparency, and it's often handy to make a 1x1 completely transparent .GIF file known as a "shim" or "spacer" that can be resized by html so the file size won't increase, but the image size will, allowing you better control of tables and the cell sizes.
Those that have Photoshop should go to "save image for web" and check out some of the comparisons simultaneously of the original, .BMP, .JPG, .GIF in quality, and file size, play with the options, you might be surprised with some results.
For Print, you usually work with .JPG, .TIFF, .EPS, .PDF, .PSD, .AI, and a slew of others. .JPG again works great for printing images and does fine with text. .TIFF is more often used because it can save layers and text, so it can be edited in pieces and is able to use postscript printing with the text and paths. .EPS is basically your .JPG of vector, any program that has any vector abilities can open this format, and many that can't can import it as a raster, plus resize it without quality loss. .PDF is good and bad because of the near infinite things of a file it can save, not just things like text, but you can even embed the fonts. The only real drawback to it is that there are so many options people often save it the wrong way. .PSD is a big preference for original files because it is 100% lossless and is compatible with pretty much everything, transparency, text, animation and so forth. .AI is used a lot because of some scale and layout options that make it the industry standard for vector.
I could mention Quark when it comes to printing but it doesn't save any files in itself as embedded, it only links to exterior files, so obviously it's negligiable when saving any type of image.
.PNG is a really useful file that will probably only get more useful later on as more applications accept it as a valid file. It's like a .BMP or .JPG with advanced transparency, unlike .GIF it is able to use different degrees of opacity, where .GIF is either 100% opaque, or 100% transparent. This will probably be of huge use to Web later on.
As for wallpapers, windows (at least XP) will accept .BMP, .GIF, .JPG, .DIB, and .PNG. But I've noticed it doesn't really seem to like .PNG's. With a max quality .JPG you shouldn't see any less quality than a .BMP but will always have a lower file size than .BMP. Which is technically the big advantage and the reason for the creation of the .JPG format, because of the control you have over compression. The compression in a .JPG is more advanced which is why it allows for smaller sizes. What isn't reccomended is saving a .JPG over and over, so keep your original files for editing (.PSD or whatever) but in a final form, no problem. The quality between .JPG and .BMP is only really an issue in programs that don't give you control over how much it is compressed or not.
Unless you're using something on the web you probably never want to compress the quality of an image. Images are optimized on the web for download speed purposes.
