Do not attempt to do this in CMYK or other color modes—the results are not nearly so predictable.
Be careful when using Levels corrections on unusual or heavily skewed histograms. If a tail is very long, crop only half at first. You can always go back and crop more. If changes seem extreme, they probably are, and you may be doing damage to the information in the image. Better to make more than one correction than to make one that is too strong and damages the image information.
Correct images with the flavor of the image in mind. If the image is in a light/bright setting, and preliminary corrections adjust the image darker, use the middle slider on the RGB composite Level to adjust the tone appropriately.
When in doubt, make the image lighter rather than darker—but don't go very far. A shift of more than 10 levels without certainty that you are making a positive correction is going too far. There is less of a chance of making an image too light (unless you are dealing with something very delicate, such as a soft, high-key image) than there is of making it too dark. Dark print will oversaturate and tends to get a little murky, and dark images are generally not as easy to view. Lighter/brighter images are generally easier to see.
If you have switched from a CMYK image to make RGB corrections, it is probable that color will remain CMYK-compatible after Levels corrections. It is good, however, to make sure before blindly shifting over to CMYK. Check your image using the CMYK Preview and/or Gamut Warning controls before converting.
If you remove highlight or shadow detail with corrections, you can actually paint that back in from the original image scan or from a snapshot using Histories, or use a copied layer and a blending technique (e.g. Blend If). For more control, you may want to use both: Paint the correction into a second layer, and use the Blend If layer function and layer opacity to control its appearance.