I guess it's not machine-related, not antivirus-related.
You need to prove that hypothesis by installing the same anti-virus your client has on a dev VM. If you cannot reproduce the slow start up compare ProcMon traces between the machines.
I believe Hans is on the money and the anti-virus is the most likely culprit, as per the correct answer in the QA you refer to in your question:
I have seen very poor performance (minutes vs a few seconds) for a newly deployed first run .Net application is the users are running antivirus software as the antivirus tool checks the newly Jitted assemblies are not malicious.
Make sure you're using .NET Framework 3.5 SP1 or above as "there are significant performance improvements in the area of startup. Particularly with WPF applications" and 3.5 SP1 includes Splash Screens.
A Splash Screen could be a quick (temporary) fix. Alas, not an ideal solution.
ClickOnce is getting pretty old now and there have been a lot of advancements in this field so why not adopt another strategy with a different deployment mechanism, such as Windows Installer and an Update Menu in the app. I detail the steps to make an MSI installer to Install to same path when upgrading application.
If you want to be strict about everyone being on the latest version instead of ClickOnce it would be better to have a web service the app pings on start up and downloads and executes the update when a new version is released.
Also, take tips from Google in this area. You remember the Jeff Atwood article: http://blog.codinghorror.com/the-infinite-version/

If you dont use ClickOnce you can use things like NGEN AND bsdiff, possibly even Google courgette.
There's some other ways to speed up the startup of a ClickOnce application discussed here.
While this may not answer your question directly, hopefully it gives you food for thought on how to identify the root cause and/or use a different more up-do-date method for rolling out updates.