With your random flashing, it's probably perfect to attach the leds via 74hc595 serial to parallel buffers. Just daisy-chain them across your robot and have the Arduino spew out random bit streams. All this takes only 3 digital pins. If you attach colour RGB-leds, probably the best is to attach the pins always in the same order and you either put random bits to all 3 colours or in case of anger just on the red channel and keep the two other channels 0.
If you want to be able to dim the leds all together, you can do that by attaching a PWM signal to the output enable of the 74HC595. That solution is probably quite cheap but has the inconvenience is that you can't dim the leds individually. This might be a little annoying for RDG leds, as you don't get all colours. I would drive the colours for the eyes individually.
Korman