I think that PCs should get advancements every two episodes; it seems about right for me. It allows for rapid-enough growth of PCs without making them too powerful, too quickly.
As far as starting advancements goes, I've started characters in many campaigns at low, moderate and high(er) level. The key, for me, is to make the tasks challenging, but not overwhelming, and also to manage expectations of less-experienced characters.
1st-level/low-powered/low-advancement characters are not going to be saving the galaxy/slaying the dragon/driving off the planet-eating supervillan. But that doesn't mean a low-level campaign can't be fun -- I love being able to play/run the "little guys" (or, to quote Mystery Men, "the other guys"). It makes the advancement of the campaign into the higher levels that much more enjoyable.
But, to each their own.
On the subject of success or failure of a mission hinging on a single die roll, I have to agree with Patrick & Thako. You always have to have an escape route (as a GM), if that critical roll fails.
Davy Jones
"Frightened? My dear, you are looking at a man who has laughed in the face of death, sneered at doom, and chuckled at catastrophe! I was petrified."
-- The Wizard of Oz