I decided to give Mike Reichmann's From Camera to Print tutorial a look, and after watching a preview clip, I thought that maybe the shadows in my Alcatraz pictures were so ugly because I lowered the yellow and red saturation before printing (to get those colors back in-gamut). That, it turns out, wasn't it.

It's still ugly. And the detail rendition in a lot of areas is poor. In the past, e.g. using Shutterfly, I've had pictures come back that matched the screen colors (though brightness was a bit of a problem, unsurprisingly). So I think I'm doing it right... But these results are not satisfying. I suspect this is a profile problem (although I usually first suspect myself of doing something wrong). Maybe there are some other guys on yahoo who have some feedback...