On this thread, someone succeeded in analog sampling at 360kHz (actually, he was operating the ADC at 8MHz--instead of the usual 1MHz--to achieve 360kHz), though I believe at reduced precision:
http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1242967991
(I believe they also achieved 10 bits precision at 124kHz).
Also of note is that gabebear is sending data at 2Mbit/s.
These figures are what we should be shooting for. Now that it has been shown to be possible, we can do it.
Since it appears the analog input pins don't each have dedicated sample-and-hold circuitry, I'll have to live with non-simultaneous sampling for multiple inputs. That's okay.
As far as using a dedicated ADC... As long as I'm running it through an Arduino, I don't think it will help my performance considerably, since it still has to be put through the serial connection, which seems to be able to do 2Mbit/s if you tweak it just right (but no more, at least not considerably more).