Starting to learn programming by being curious enough to hack around on PC games seems to be a common theme. Being stubborn and willing to struggle for a few years to figure out what you're doing seems to be crucial as well. I do wonder if modern / closed mobile platforms (and shorter attention spans) are going to let the next generations have the early programming experiences that kids "hooked" enough to spend the time it takes to love and learn the craft.
Working with Paul is one of the things I miss most about working at YC. Besides being interesting to talk to about pretty much any topic, I remember analyzing the data on how accurate YC partners were at reviewing applications to YC and Paul being top despite spending the least amount of time reading each one.
As someone who just started working at a startup, I definitely resonate with the idea that you learn a lot more quickly and get to operate above your level. Of course, for him that meant creating Gmail.