A friend of ours recently gave us a number of photos of flowers, printed on a metallic paper from mpix. The result is subtle, but quite pleasing - there's an extra brilliance to the whites in the pictures, and high-contrast lines seem more distinct. For largely aesthetic pictures (e.g., nature pictures) I think I'll be trying this out in the future.
The pictures costs $0.59 for a 6x4. They also have options for printing on matte and a couple other formats. Normal 6x4s are $0.29, so I'll probably stick with Snapfish for normal photos, where they costs just $0.19.
My computer-self wants an API for saying "I want to print the photo at the given URL". E.g., mypix.com/api/print?url=http://my.site/photo1.jpg - do any services offer this?