Thinking about it some more, my project requires pushing a 24-bit 16x40 pixel display over the air at 60Hz, which is a data rate of 115200 bytes/sec = 900kbps, which from my reading seems to be well in excess of what Bluetooth can deliver. So that means 802.11b/g wifi, for which under 1Mbps should be a walk in the park.
Therefore, the combination of the Arduino Pro
shield being fed by off-board storage seems to be a more practical solution.
I'm pushing the RAM on the ATmega328 hard though, I might even have to look at an ATmega2560-based board.