sending them to Mpix.com for physical printing
That makes it easy: check their web site or email them and ask what export process gives them the best results. Make sure to tell them what you expect from the prints: are they vacation snaps? Paying customer prints? Art prints? If they say JPEG for everything you might want to consider a different print company. (JPEG is fine for small prints, but if it's an "art" print you'll get better sharpness and tone gradation from a lossless format)
You might want to wait for more responses here: I actually don't do a lot of printing, so other folks here might be able to speak from greater experience.
This may be a stupid question but are there any companies that print anything BUT jpegs? I don't mean what file formats you can send to them but what they actually end up using.
I'm still under the impression that of my 5DII files a big chunk of the information will not translate to any print really (especially at sizes like 8x10 or smaller) since resolution in the digital age is limited to about 300 dpi - which makes an 8x10 print, what, a 8MP file or so at best. So essence it comes down to the question who or what will do the best job resizing your image, you in PS/LR or the company's printer software.
Do I have that approximately right?
Also: I am still also confused by the sizing and exporting functionality of LR3 since it works significantly different and uses other terminology than PhotoShop CS5. I haven't figured out the exact meaning of the percentages for jpegs yet and how they relate to the 12 quality steps in CS5.