I've done this with a tiny MCU using pulse dithering. It did exactly the effect you want, too. You need an MCU, three drive transistors, and your lamps.
Note: an MCU three PWM modules can do this in hardware, the software just programs the PWM counts as needed.
What is pulse dithering?
Consider pulse width modulation - for every N clock ticks, the output is on for the first M of them, and off for the remaining (N-M) of them. Your period is limited to 1/Nth of the clock frequency, though.
For pulse dithering, you spread the M "on" ticks evenly throughout the N clock ticks, so your "period" is effectively the same as the clock frequency. This lets you have more precision in your "brightness" setting, while using a slower clock speed. Of course, your real precision is still limited to clock/60Hz.
The algorithm is amazingly simple, and best implemented in an assembler interrupt routine (due to the use of carry):
int setting; int count;
interrupt() { count += setting; if (carry) light_on(); else light_off(); }
A larger setting will overflow more often, causing the light to be on more often.
You may even get away without conditionals:
mov #0,bits add count_red, setting_red rolc #1,bits add count_green, setting_green rolc #1,bits add count_blue, setting_blue rolc #1,bits mov bits, gpio_port