How do large companies handle software updates for users without administrative rights?

Windows Server Update Services (WSUS) provides the server-side component to handle update deployment. Its provided by Microsoft as a no-cost add-on to Windows Server 2003 and up.

Computers (client PCs, servers, etc) are typically directed to the WSUS server to receive updates by way of Group Policy settings (that can also be done through simple registry manipulation, too). The Windows Update client software is configurable to allow the client to automatically download and install updates on a schedule, or to download and prompt for installation, etc. The client software can force the PC to reboot, or may optionally defer reboot if a user remains logged-on. There are a variety of options.

For third-party software you can create updates to distribute via WSUS by using the Sysmtem Center Updates Publisher as part of the Microsoft System Center Configuration Manager product. (There are some other tools that will allow you to publish non-Microsoft updates to WSUS, too-- I have no experience with them and can't recommend / comment on them. There's some talk about them in a comment to this Server Fault answer.)

I typically install software to client computers via Group Policy, so deploying updates typically involves rolling new packages that way. You can see more about that strategy in this Server Fault answer.

BTW: You're doing the right thing re: getting rid of Administrator rights for users. You'll see a dramatic improvement in PC reliability, and indirectly you'll be improving security. Having a network with client computers having restricted Administrator rights is a very nice place to be. At the very least, malware will be restricted to damaging the profile of an individual user, which makes cleanup as easy as restoring a copy of a pre-infection roaming profile from backup.

WSUS looks like it would be perfect for you.

Best of all, if you're running windows server in your environment, its free!