Batch your patches
One way of minimizing downtime due to patching systems is to batch a bunch of patches together and apply them in one shot. With critical security patches released by Microsoft, you can typically use the /z patch for update.exe to apply a patch without rebooting the system afterwards. Then you can create a batch file of start update /z commands to apply a series of patches in one shot, afterwhich you can reboot the server.
Unfortunately this approach doesn't always work. For example, some IE updates don't support the /z switch, and some Windows Media patches don't either. When in doubt type update /? for each patch to see what options they support.