EEG signals are small, ranging from 10s of microvolts to less than a millivolt.  If you don't amplify it enough, you won't be able to sample it with appropriate resolution. I'd advise against trying to amplify in one step with an instrumentation amplifier to a level sufficient for acquisition by ADC.  

You need to account for electrode offset potentials.  As a rule of thumb, I like to allow for about 150mV of offset.  If you go much beyond a gain of 20, you're almost guaranteed to saturate your instrumentation amplifier.  

The general approach should be modest gain with an instrumentation amp, followed by a bit of high-pass filtering to remove your offset, then some op-amp stages to bring the gain enough to record by ADC.  This is, in fact, what's shown in step 2 of the instructable.  

As to where to put the ADC and noise concerns -- if the noise is higher frequency than half your sample rate, then you MUST remove it prior to the ADC or it will alias.  If the noise isn't aliasing than you can remove it with digital filtering techniques after you sample.  That said, it's often better to remove the noise before you amplify it!  It might well be bigger than your signal in this case.