I am using a library recently posted here in the forums (ShiftMatrix) to run a 48x16 LED matrix. When applied to a RGB matrix this becomes 16x16, as RGB LED's have 3 actual LED's inside the one body(so 48 / 3 = 16). This is 265 individual RGB control with 32 levels of brightness per each channel (Eg. 32x32x32, R G B). This will give you lots of colors. This is all achieved with shift registers and some transistors. Check it out. The library is very easy to use.
Also as far as I can tell using a Matrix will save on power consumption as you will only have one row or column on at a time. So only one set of lights across the panel actually has power at any one point. For the matrix I describe that would be 48 x 20mA = 960mA for the LEDs plus some more for the Arduino and the Shift Registers. Would still be under 1.5A, at 5v that would be 7.5watts(at most).
This is just one other way it could be achieved. See what works well for you.