We install SEP across 6 sites, some connected with bandwidth like yours, using the usual combination of:
- DFS install shares to contain the Setup files
- DFSR to replicate the setup files efficiently and in near-real-time to branch office servers, and
- GPOs with custom MSTs to install the feature sets we want.
We restart servers after hours using Task Scheduler to get them updated ASAP, and workstations by asking people to reboot (works with 60% of the people). Patch Tuesday or the occasional crash takes care of the stragglers. There's enough randomization that we've never seen a bandwidth shortage, but our largest site is 120 machines with gigabit, so that's not a very large site.
Once you get it set up the way you want, it takes only a few mouse-clicks to push updates. Group Policy can also handle the problem of upgrading from (for example) MR3 directly to MR4 MP2, skipping MR4, using a Symantec-supported upgrade path. Set the Package to do a Replace install...remove the old version, then install the new one. Then you don't have to do MR3 to MR4 to MR4 MP2 because MR4 MP2 is installing to a machine with no prior SEP version on it at all.
As a bonus, when it's done, no restart is needed. If it's needed, it's already happened before the user ever logs on.