One person reported a 3 second delay. That's a noticeable delay! It could have been caused by internet access times, too. You are doing a direct connection, so nothing (like a router) will be delaying with your transmissions.
I'd still suggest thinking about how you will "notice" a delay. What do you expect to happen, and how will you measure this delay? After you press a button (human speed), do you expect to see all 4 lights change within a fraction of a second? Let's set 100ms as the max delay.
At 9600 baud, you could send 100 characters in that time. Unless your command is really verbose, that should be no problem. If you send a different command to each light (i.e., they each have their own "name", or address), you could send 25 characters to each light.
Or, are you wanting to continuously change the lights' colors? With the above max 100ms response time, you could change the colors at least 10 times per second, at 10Hz.
If your commands are smaller than 25 characters, say 10 characters, then sending individual commands to each light would take 40 characters, or 40ms @ 9600. Then you could change colors at 25Hz. If the lights were blinking on and off, it would be noticeable. Annoying even. But we're talking about changing colors, so if it's a gradual change from one hue to another, 10Hz or 25Hz will probably not be noticeable.
You get to choose the commands. One of your Arduinos send them, the other receives them. It could be as simple as "FF0000," for all lights to turn RED. The comma delimits the RGB "tokens". If you notice weird colors flashing on, you might be getting data errors. Just add a checksum or CRC to detect bad commands and ignore them. Then your command might be "00FF00A9," a grand total of 9 bytes.
By the way, here's how you calculate the time it takes to send a command:
time (seconds) = bytes * 11 / baud rate
For 9 bytes @ 9600 baud, it takes 0.0103s, or 10.3ms to send. Not very long. At 115200 baud, it only takes 0.00086s, or 860 microseconds, an absolutely imperceptible time!
However, if they're "near" to each other, it's easier to notice that they don't go ON or OFF at exactly the same time. If this is for Disco lighting, you could use a "broadcast" command (to all addresses) to make it happen nearly simultaneously (within 1ms or so).
With only 4 lights, I can't think of a reason that 9600 baud would be too slow. As long as you don't use delay(1000)
in your program, you should be fine. 
Cheers,
/dev