Funny, I just placed an order online to get some test pics printed.
As for sizing, 4x6
is standard, as that's the 2:3 ratio of your CCD, although from what I've seen from a friend's photos, it's too small for anything other than family shots. 8x12 would be the minimum, I think, but they're more expensive.
This place does 8x12 for $3, and they also allow a lot of control when printing; if you have a non-standard size, you can choose where you want the whitespace to go, etc. I haven't used them, but after a lot of searching online they seem to have reasonable prices and are photographer friendly.