I would think that a lab's color-correcting quality is dependent upon the lab and the skill of the technicians. There probably is not a single, globally correct answer here, as every lab will use different equipment and have different people with different levels of skill. That said, when it comes to color correction for print, taking the paper into account can have a keen impact on the quality of printed color.

I would say that if you give the job of color-correcting an image to someone else, you are always giving up your own personal creativity and style. A lab can't really know how you want your photos to look, and regardless of how skilled the technician may be, they will only be able to make a print look good according to their own vision. If you want to have as accurate a color as you can, you could try asking for ICC color profiles for the lab's print gear and paper, and use Photoshop's soft-proofing to ensure that tonal range is bound to the range of the paper, and that your photo does not include any out-of-gamut colors.

Black point in particular can be a key factor in determining if a print renders subtle shade nuances correctly or not, and that can affect the overall appearance of the image. Blocked blacks can suck up a lot of fine detail that may be important. It can result in an increased level of contrast that is undesired. Sometimes you need to choose a paper that is capable of achieving the contrast you desire, as some papers simply can't support high contrast without losing important detail while others can.

Some papers, particularly fine art papers, often have odd gamut boundaries, and highly saturated colors are often out of gamut. When printed without manual correction, colors may shift, or they may simply be clipped, resulting in odd gradations or unexpected tonally flat areas. Inks used can also be a factor here, and if you have photos with particularly saturated colors, you may want to make sure the printers use inks capable of achieving a wide enough gamut to accommodate your needs. Gamut issues like that can be difficult to correct without affecting the rest of a photo. Correcting such issues with a single specific goal (i.e. always balancing for skin tones) can sometimes have detrimental effects to other parts of a photo that may affect the rendition of your personal style. If your photos are not portraits, correcting for skin tones can have a severe impact on the quality of color, such as mainly green landscapes, or landscapes with richly saturated sunsets and the like.

If you want to end up with a print that fits your personal style and vision, it is probably best to request an ICC profile and use the soft-proofing features of Photoshop to identify problem areas at the very least. If you have the option of correcting those problem areas, and having a small-scale print made (i.e. an 8x10 or something like that) to see if your corrections result in the outcome you desire, you'll have the best results. If you do not really have a specific style in mind, you could probably get away with having a lab do color correction for you. Again, it might be best to see if the lab can send you a smaller size sample print before spending big bucks on a larger print or a set of prints.