They can certainly share a 16MHz crystal if the traces are of total capacitance less than that required to load the oscillator (guess 10pF/20cm for 20mil traces) and Too MuchTM noise isn't injected somewhere along the line.
Synchronization between Arduinos, however, is a different beast. First define your maximum allowable phase variation for the project to work. For better than 63 ns synchronization I suggest a new question that asks how to do that, without any IC or oscillator constraints. Interrupts other than the triggering one, that which fires to light the LEDs, need to be ignored for sub-microsecond performance. From about 10 µs to 100 µs, so long as all interrupt service routines (ISRs) are what is known as "thin" (in this case it means they return in less than 10 µs), the micro can perform some other simple tasks, but nothing like serial communication or other continuous duties. In the 100 µs to milliseconds range the micro is free to perform some more demanding interrupt-driven tasks like sub-115200 baud serial communication. Once in the millisecond range one can afford to program ISRs in something other than Assembly, allow sequential as opposed to concurrent signaling (ie: they can be chained), and generally not worry so much about synchronization. Above 10 ms our brains begin to detect flicker.
The above is full of guesses, abouts, and arounds.