[andrewla]

I think this is a bootstrapping problem for all new coins. As you say, novel mining methods are vulnerable to cloud-based "attacks", and existing mining methods mean that the economics of competing with the main coin's mining power can make you vulnerable to sharp swings in mining power.

As unpleasant as it sounds, a centrally managed coin is probably the only effective way to bootstrap a new coin securely at this point. A trusted source or groups of sources has to sign off on a "main" chain periodically until there is sufficient mining capacity that the cost (in coin units) of bringing new capacity online has reached some sort of equilibrium, after which you could soft fork to remove the signing requirement (or just release the private keys for any miner to use and let the consensus algorithm take over).