I believe I've found what's causing the large delays. It's the 100nF cap that they put across the AREF pin. I didn't even realize it was on the pin because at first look I didn't see it on the schematic because it's tucked away in the top corner.
I breadboarded the ATMEGA and ran the tests both ways with and without the capacitor. With the cap I saw the standard 3.5ms switching time (D-I) and without the cap it dropped all the way down to 12.7us . There was a large improvement in the other switch time (I-D) from 3.75us down to 15ns without the cap.
I tried the same test with a 10nF cap and the two switch times were at 359us(D-I) and 435ns (I-D). Using the input impedance of the AREF circuitry (32k ohms) these times make sense if you calculate the RC time constant.
Those are some good ideas Dave. Another suggestion would be an "averaging" analogRead (ie analogReadAVG(pin,samples_to_average)). I'm guessing a lot of people take sensor readings by embedding the analogRead function in a for loop and average the samples, might be nice to have that all in one function.