The intermediate cause and workaround for this problem is with User access to .NET cryptography files used by a password-protected database. The problem was solved by changing the permissions on the folder.
You can open command prompt with Run-As Admin and issue this command (Win XP)
cacls.exe "C:\Documents and Settings\All Users\Application Data\Microsoft\Crypto\RSA\MachineKeys" /E /G Everyone:R
I also added this comment to my code near the SQLCE connection string code:
/**************************************************************************************
* To get rid of the slowdown on non-admin users you need to grant them read access to this folder:
* C:\Documents and Settings\All Users\Application Data\Microsoft\Crypto\RSA\MachineKeys (XP, 2003)
* C:\Users\All Users\Microsoft\Crypto\RSA\MachineKeys (Windows 7 or 2008)
**************************************************************************************/
This issue is mentioned here: SqlCe opens slow under a limited user account in Windows XP
Note: on the problem machine, the ...\MachineKeys folder was visible in WinExplorer, but the files couldn't actually be read. "Everyone" had "special" permissions that didn't allow "Read". I think .NET may have been installed by Domain admin, not local admin.
This is only a workaround. I still don't understand why the folder had weird permissions on a few machines but not the rest. I am deploying with ClickOnce, so I can't change the folder permissions automatically.
I have only seen this problem with XP, and other posts imply that this is just an XP problem, so hopefully I won't have to worry about it for long...