Find a copy of Bill Bowden's 'Fading-Red-Eyes' circuit, uses 2 opamps to create a low frequency triangle wave. Build three of them, all the same, except the LED and limiting resistor (which you will need to match for each color). I used larger capacitors for a longer fade. It looks better than any microcontroller job I've seen or done, although my AVR is pretty good for just an 8 pin chip and RGB LED (no regulator, resistors or capacitors).
Anyway, back to the opamp circuit... The compnent tolerances will give each color a slightly different frequency, but pretty close. Don't think anybody could sit and stare at it long enough to detect any pattern. It's a simple circuit, but gives the best results I've seen. Forget 256 colors, there will be millions.