Due to small memory, I must cut down the sampling rate to 8 KHz, but shall I keep treating the sound as if it has a 16 KHz sampling rate?
No if it is sampled at 8KHz then treat it as 8KHz.
So what actually makes it faster?
Speeding up the clock that drives the successive approximation A/D. It means it spends less time on each bit's decision.
Correct me if I'm wrong. Digital stereo audio stores its samples by alternating all its channels. For instance: if the data is stored in an array, then the even-numbered indexes correspond to the samples of the left channel, and the odd-numbered indexes correspond to the samples of the right channel.
While that could be used it is not the way it is normally done. There is a separate buffer for each channel and it is possible that one channel compresses more than the other. If they are interleaved like this then you can't apply any compression later on.
By using analogWrite twice per loop (in order to update the duty cycle of both channels), will this create a sort of "phase shift" to the right channel? (if the left one is updated first)
No because the analogue write update does not happen immediately but only when the clock gets to a transition. As this time change is way above the filter's cut off frequency then in effect there is no phase shift.