I'm not sure the way he is averaging now is doing anything beneficial since he just averages short bursts of values. Implementing a moving average filter might improve the signal, but Max would need to implement a circular buffer for the spectrum values in between channel reads.
Some Notes on moving average filters, that seem to be missing from the Wiki.
A moving average filter implements a sinc function
H[f] = |sin(pi *f *M)/(M*sin(pi*f))| where M is the order of the filter.
The full sampling frequency is divided into M humps.
The peak at the center of sampling frequency has an amplitude of 1/M for odd M. The peaks near the center will be close to this value for even M.
The amplitude of the second hump that occurs at 1.5/M approaches 1/1.5pi as M gets large.
If you do this though, you need to make sure that you initialize spectrumLeft[i] to zero in your startup code. This is the simplest form of IIR (Infinite Impulse Response) filter.
The averaging technique your friend Steve showed you is most useful if you have a lot of noise on the analog signal which might occur if you had long wires or you were using adjacent signals to run PWM to a motor or something similar.
Your timing diagrams look similar to the ones I have for my pipe organ playback and paper roll conversions. May be some similarity here as music is recorded as discreet 'events' which relate to frequency (pitch) and duration.
My preference on the Arduinos when dealing with sample and hold type shift registers, is to cascade the hardware timers. This is how the USB scanner I showed at EELive! works.
One timer is set to the width of the clock pulse. This toggles the clock line through the output compare. The cascaded timer (which can be done through the timer configuration) counts the clock pulses and can toggle the output compare pin automatically to generate the strobe. This keeps the ISR routines small. The overhead plus a shift of the bit in or out.
For really tight constraints, Unrolled loops work well. This is a code space/clock speed tradeoff. AVRs have a lot of code space.