Hardware requirements for 22khz audio with PIC microcontroller

We've spent quite some time looking into different implementations of playing audio from an SD card. There are quite a few out there, using both PIC and AVR (atTiny) . Rather than just use some existing code (although we're not ruling that out completely) we've been thinking about how to implement audio playback on a microcontroller.

At first, it seems quite straight forward: get a byte or two of data from an SD card, send to a PWM routine and make a speaker vibrate. The numbers involved don't sound too shocking either - until you start to look into them.

For example:
An audio sample recorded at 8-bit, 22khz requires the variable voltage on the speaker to change 22050 times per second. That's not a bit deal. Is it? We've millions of clock cycles and need to vibrate a speaker tens of thousands of times a second. No problem! Surely?

We're running our microcontroller at a maximum of 16Mhz (because the max supply voltage is 3v - for USB and 5v designs, you can go much higher, but at relatively low voltages, the maximum oscillator value is affected. The maximum speed you can run a low- to mid-end PIC at about 3v is 16Mhz). With an 8-bit PIC, the operating frequency is fosc/4 (i.e. one instruction takes 4 clock cycles). So running at maximum speed, from a 3v (2xAA battery) supply our PIC can do 16/4 = 4MIPS (million instructions per second).

That's still not shoddy.
But when we consider that we need to change our speaker voltage 22050 times per second, we must divide 4 million by 22050. Which is 181.4
So every 181 clock cycles, we need to change our speaker frequency.
And changing the PWM speed will eat into these precious clock cycles.
Which means we're going to end up with actually very few clock cycles for reading the data from the SD card.

Conclusion -
We may end up down-sampling our wavs to 11khz or lower to get a reasonable playback sound. Or we might just have to move over to AVR/atTiny and "borrow" some existing code!