Those are very nice questions. In fact, if you keep cooling pure water enough, it will freeze spontaneously, without any added nuclei. Likewise if you get the water vapor super-saturated enough (say by cooling it), it will start to condense without any added nuclei.
That still leaves your basic question. Let's say that we've got vapor (or liquid) that's supercooled but not enough to condense (or freeze) without some added nucleus, at least in any reasonable period of time. Why does it act that way?
Let's look at the liquid. It should freeze when its free energy can be lowered by forming crystals. That means that the energy it can lose per molecule, U, exceeds TS, where T is the absolute temperature and S is the entropy lost when the molecule lines up into the crystal. So you can see why this tends to happen at low T.
Ok, so here's the point. When you add a molecule to a big crystal, you add energy-lowering contacts on all sides of the molecule. That makes a big U, which can exceed TS. When you add a molecule to a small crystal, the surface is still very important, and there isn't so much good contact per molecule. U is smaller. If it's just below the freezing point, the free energy actually goes up
as molecules are added, until a large enough frozen cluster has formed. Things don't form high free-energy clusters very often, since higher free-energy means lower probability. (That's why there are fewer air molecules high up, where their energy is higher.) Just below the melting point it takes more or less forever before a big enough cluster is likely to form by accident.
A very similar argument describes the formation of liquid clusters out of a gas.
Follow up if this needs more explanation.
(published on 06/27/11)