Well, definitely not at startup unless the updates are really quick to perform. The computers at our school update at startup and it's a nightmare. Sometimes a PC takes half an hour to boot for this reason.

Also, letting your users manually choose wether to update or not in a dialog is not a really good idea either because many users don't see why updating is important and always click no.

I think shutdown (not reboot) is the best moment because the user doesn't need the PC anymore. This can however still cause fustration if the user wants the PC to shut down quickly.

So I think this is a good idea:
1. Download updates while idling. This can be easily implemented by putting code in a screensaver. When a user resumes his/her session, pause downloading and continue when the user is idling again.
2. Every week or so, at shutdown, finish downloading if not yet fully done and install them.

This is a good way of instating updates at shutdown while still keeping shutdowns not that long. And only doing it every week will lower frustration too.