Also a lot depends on your level in electronics and in software. Some chips greatly simplify hardware design, and there is on-line library to communicate with IC ( TLC5940, MAX7219/7221.), so no problem on software side, but they cost more.
WS2801 / WS2803 is good choice, as it has serial interface, so less wiring/cables work.
To make life easier, you could find addressable RGB strips, that works with arduino, than all assembly boils down to hook up 4 wires.
To have learning experience, look into 74HC595 IC, it's cheap, but more complicated to communicate with. I'm working myself right now with this register, 9 IC, 72 PWM channel, arduino kicking SPI train commands set, in 38 usec, every 125 usec. No assembly so far!