option 1 is undoable...
it would mean that all the clients have to ask ALL others clients if they are going to update and based on the answer the client asking will or will not update while others are updating.... i believe your 20 minutes will become 20hours that way..
I believe (not sure cuz its been a while since i read the manual) that the clients start checking every 45 minutes for updates, either for the VPS or for policy changes. Meaning that if you start clients at different times they should check different times.
You can also change the interval from 45 minutes per group then i believe.
meaning you can differentiate the importance and the time of a group for checking for updates and actually updating.
1 group could be set to 30 minutes which means every 30 minutes that group checks and updates
another group for 45 minutes
another group for 60 minutes
its not an ideal sollution tho...
But if you have over a thousand VM's you should also check into the hardware capabilities.
Where is the bottleneck, which software is used for the virtualisation, which hardware is used?
If you run blades you should check which networkcard and virtual switch are the vm's on.