How long should we wait before deploying Vista / Server2008 SP2
I would give it at least a week before installing on anything but a test machine - I've never seen an emergency Service Pack retraction more than a day or 2 after release.
The next step is to deploy as fast as possible - it may contain security enhancements not in SP1 + Automatic updates. Part of deployment planning is testing in your environment. This would apply equally to system types 1-4 above. Vista SP2 does not have Server 2008 SP2 as a prerequisite, so this can be installed in any order.
If there are incompatibilities with SP2 and your environment, the actual timeline for deployment may be many weeks as these are resolved by either the application supplier or Microsoft.
In theory you've already tested application compatibility with the RC on a test system and server. Now that it's released the time to apply it is now. You should make a backup of your standard desktop image and apply the RTM version. After a quick test on your system (assuming you are not already running windows 7 RC) roll it out to a few test users (number 2 on your list) and after verifying that you have backups, roll it out to the standalone machines. (#1). While your users are verifying that it won't break their copies of solitare, you can chedule the reboots and downtime to deploy it to your 2008 servers. All of your servers should have a backup. This is critical as I have seen servers go belly up during the RC due to driver issues (servers that did not have updated drivers). If you've kept up on driver updates you can apply the SP2 to windows servers. (#3). You should now roll out SP2 to the rest of your userbase. I'm not sure by what you mean by "critical" windows servers. I'm guessing that those are nonredundant servers with high value business functions (which begs the question how critical can they be of they aren't redundant?). Ensure that they are up to date on the firmware/driver front before applying the SP and after a few days on the other servers I'd finalize the rollout.