A couple of tips:
Regardless of how you choose to do it, please don't create a new service or process to check for updates and then leave it on continuously. You know, like Adobe and Sun (for Java) like to do. Regardless of what you're making, I can guarantee that it's not important enough that it needs to be updated every time the user starts the computer. Updates should either be integrated with a standardized update process common to the OS or when the application is running. Updates should not continuously steal system resources or slow down the boot process by default.
If you maintain separate directories for each version, you need to add code to maintain that. Disk space is not intended to fuel updates. I recall one Citrix application that had 5 different versions on my computer at one time. The user should not see more than two copies (maximum of one backup, confirmed as functional) of your application on their file system unless they explicitly placed them there. Shortcuts to your application can become outdated when the folder location changes like this, so be careful.
If you update after the program has been started, I would recommend notifying the user in a non-obtrusive fashion. If the update doesn't cause a significant change in functionality, download the update in the background, switch to the new version the next time the application is executed, and notify the user of significant changes (don't use a modal dialog or steal focus). Don't make the user click a button to agree to install updates before launching the app, or force them to restart to use the updated version. Allow users to configure automatic updates, then do it without impacting their productivity. Firefox is rather bad about this, which is sad since it's such an integral application to many users.
Don't touch the system tray. That should be reserved for useful (to the user) applications. I'd also recommend against balloon notifications, as well. Use something like the infobar commonly seen in browsers. Microsoft applications are particularly bad about using the system tray and balloon notifications to waste user time with unimportant notifications. If the user enabled automatic updates, they really don't need to know that everything is working just as they expected. Tell them when there's something new or useful, and don't force the knowledge down their throats. Leave the changelog under a Help menu item so they can check bug fixes on their own.
Be careful of updates using the MSI system if you deploy a default configuration file. You don't want to overwrite any user files in your update. In the same vein, if the format of configuration files or user files changes, you should provide a mechanism to automatically backup and upgrade those files. Or start building default settings internally within the application instead of deploying them.
Be bandwidth conscious. Large files take time and possibly metered bandwidth from your users. Especially if you update daily.
I can't recall a truly non-intrusive update procedure off-hand, but I can recall plenty that have wasted my time and resources in the past. Don't be the guy that makes another.