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 (Even if you just wanted to do a quick web search...).

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 installing updates at shutdown while still keeping shutdowns not that long. And only doing it every week will lower frustration too.