I don't know what kind of printer you're using, but using 800x600px for an 8x10" print, or 1280x1024 for 11x17" nets you around 75dpi, which will produce terribly pixelated and jagged looking shots. They're the ones that people see and immediately comment, "Oh, you printed these from your digital camera, didn't you?"
If you want a quality printout, something that rivals 35mm film developed at a photolab, take a few steps in the right direction:
First, go out and buy yourself a dedicated dye-sub photoprinter (the Epson Picturemate was the best $200 I spent this year).
Next, print at 300DPI when possible, and never below 150. This means that a 5x7" requires 1500x2100px; an 8x10" needs 2400x3000px. The high pixelcount is not an outrageous request when you consider the abundance of >4mp cameras and the hundreds of GBs readily available today. A single DVD+R/W disc can hold over 4GB of data!
While you're at it, activate the printer's enhanced detail setting, which increases the number of passes the print head makes on the page. Some may complain of long print times, but I certainly don't mind waiting an extra few seconds if I end up with a shot that people can't distinguish from 35mm film and lab developing.
I do agree with your comments on compression; you face the law of diminishing return when jumping from JPEG to BMP or TIFF -- the tenfold increase in filesize just isn't worth the 1-2% gain in quality achieved by lossless compression. But compression can only take you so far, and DPI still reigns king when it comes to making prints.