Some .apps only open via sudo /Applications/*.app/Content/MacOS/* I have a few that after install will refuse to open - no error. The first time they may appear in the Dock for a second or two; then disappear.

It may or may not be a coincidence - but both have 'storage management' in common: SeafileClient and PydioSync. Perhaps more likely to be relevant - both are also using Qt. (It is a coincidence).

If I run in terminal from /Applications/[name].app/Contents/MacOS/[script name] then in some cases I see the process exit with an uncaught exception: NSException.

I can find no similar complaint for either, and have tried a couple of versions. In other words, I'm fairly sure it's something weird with my system.

I've recently reinstalled OS X, and am on 10.11.3. The issue persists after reboot.

After a bit more digging, I've found - bizarrely - that if I launch with sudo, they work fine. Completely fine. But after closing either via the app or the attached terminal, they still won't open normally.

I didn't do anything odd to install these - two were downloaded .dmgs, and one was an Homebrew Cask. Other apps function fine.

Any idea what may have caused this, or how to fix it?

Permissions set to 755 (anyone can execute) in all cases.
Did you perchance move your user directory? If so, I suspect what's happened is that the owner/group of those applications is not the same as "you", and that's why they work under sudo and not normally.

I had this happen to me when I got my new computer. For some reason the machine refused to use the user/group ID from the old machine, and thus I wasn't part of the user/group who had access to things. I was able to fix most of this by selecting my user folder, Get(ting) Info, and then using the gizmo at the bottom to take ownership of everything inside the folder.

I also recall that there were lingering effects elsewhere, but I don't specifically recall apps being a problem. Nevertheless, I think you want to check to see if you have write access to the various /library folders, both in your own user folder and the system folders. Just try saving a text file into the one in your user folder and see what happens.