Recommended install folder for multi-user scenario

I've searched through dozens of forums and still haven't found a clear answer to the following scenario:

I install our solution on PCs that are used by multiple users in a shift-work and shared-PC environment. That means that a single PC could have literally dozens of users that log into it. This is very similar to the scenario described in http://discuss.joelonsoftware.com/default.asp?biz.5.825284. We previously deployed using ClickOnce which is obviously not an ideal solution for that environment... enter wyUpdate!

In an ideal world the hope would be to install the application in the traditional manner to "C:\Program Files\My Company\My App" directory. While we can do this, it obviously makes updating the application more difficult, especially given that many environments that I install in do not give users local Admin rights (not to mention that it's not considered best practice). The closest answer I seem to have found is the general idea that "updateable apps" should be installed under each user profile (ie. AppData). But this leads me back to the above paragraph - having to install and maintain upgrades in those environments is exactly why I was switching away from ClickOnce.

In the Forums I've seen mention of assigning FULL rights to Users to the program directory and mentions that the program directory should NOT be off the root and should be available to all users. So what is the recommended install directory in this scenario? Do I install to C:\ProgramData? AllUsers\AppData (this was explicitly identified as not-recommended in one of the forums)? Into Program Files but change the rights? If the rights need to be assigned is there a recommended link to do this programmatically (I've only seen links to do it manually, which is obviously not ideal)?

So to reiterate:- What is recommended install (and application update) folder for an application used by multiple users on the same PC?- Are elevated permissions required during initial install?- Do special rights need to be assigned and, if so, what is the recommended way to do this programmatically?

Thanks