Do you really need 24 bit color depth? ... I don't believe there is any other way. Unless I've missed something, the LPD8806 takes 8 bits per channel per LED.
Do you need the LEDs to be individually colored or can you use a color palette? ... I'm not sure what you mean by a color pallet. I believe the LPD8806 takes 24 bits per LED regardless?
Reduce the storage requirements. At the point the data is sent it would have to be "expanded" to 24 bits.