What's a "rich" black

The question only applies to CMYK work.

Costco I imagine is expecting RGB images, at least for the photo sizes, because the average photographer might not even know what CMYK is, and would certainly not know how to create it. Of course, the photo printer must convert rgb to cmyk internally but that's not something you have control over -- but if you did send them a CMYK file, chances are they would convert it back to RGB to be compatible with the photo printer, like most non-postscript desktop printers do.

For the web, you definitely need RGB because that's what the end user will see on the screen. I suspect that many browsers would render CMYK images badly if at all.