I use walmarts service and have since 2003.
They crop, a lot. I add a white border (that scales to 1/4" on a 4x6) in image editing software. This negates this issue somewhat.
They also "autocorrect" my color and contrast on self-scanned stuff. To fix this I add one pure white pixel in a light spot and one pure black one in a dark spot. Digital cameras usually don't need autocorrecting but sometimes I'll "burn in" the sky and clouds for example before I upload.
I've printed 1024x768 to 4x6. You can tell it's digital from a few feet away. But so what? The colors, if not messed around with, are way better than you can do yourself with a consumer printer. And being processed on photo paper with chemicals, the prints are archival. (Home printer ink is suspect.) These still make great snapshots for my elderly grandparents who love to get stuff in the mail and handle the prints, put them on the fridge, etc.
You can pick any walmart to send prints to, so if you have relatives across the country you can prepay and have them pick the prints up at their local store.
I've sent regular 35mm away, scanned the 4x6 prints I've gotten back at a high dpi, and uploaded to walmart for 8x10s. These look good and grain free with no digital artifacts. I set my JPG resolution to ridiculously good, you have 4 mb upload limit so why not?
XS650 is right about digital resolution, you might as well set your camera to "max" if you're taking a shot you think will be a keeper. As memory prices drop this should be standard practice soon.
Whatever you do, back your computer's picture folder up to CD-ROM frequently too.
