The best protection about noise or "grain" as some have called it, is to expose the shot properly. Any time you try to brighten an image, even if you start with a RAW file, you're going to add noise.
In practice, you want to have the histogram as close as possible to the right edge without touching it.
You should also apply noise reduction prior to any sharpening to prevent the sharpening from exaggerating the noise.
NoiseNinja and Noiseware both have PS plugins to help with this stuff.
Even when you have an extreme noise problem, like in that first shot, there's often much improvement that you can do: