In the Netherlands I've always used profotonet.
Decent prices, great quality prints, quick delivery times, and most importantly: the least hassle with payment ever. You don't need a credit card or paypall or similar for payment. all that's required is a valid email address, mailing address and optionally a different billing address. They'll send you the bill digitally, and also a paper copy with the photo's and ask that you'll pay them through your banking account.
They immediately start printing after you've uploaded your photo's. Usually you'll have them within two working days, sometimes even one (depends on time of ordering (before or after noon) and size; packages take longer than envelopes). Of course, they only deliver within the Netherlands, so I guess that's how they minimise their risk (you can be tracked down if you don't pay).
You can upload via the browser (they even a plain old HTML 4 website for dire situations), or through a downloaded little program. Paper types that can be chosen are: glossy, matte, "Fuji Digital Professional DP II Glossy Pearl", and for the black & white fans: Ilford glossy or lustre.