This attack shows how using a myriad of AuXPoW chains could avoid this problem. As by using a myriad of chains then the attacker would need to attack more than one chain. While using AuxPoW with the biggest coin on each chain would greatly increase the network hashrate. I think you should quickly adopt AuxPoW with litecoin how Dogecoin has just done so to help stop any potential future attacks. Then the myriad with NeoScrypt Feathercoin merge-mining and Lyra2 Vertcoin merged-mining can brought in a later date. Plus it may be worth including Cryptonight Monero AuxPoW with the myriad. Plus possibly X11 Darkcoin merge-mining included in the Myriad. To have a total of three to up to possibly five myriad chains all in AuxPoW with the biggest networked coin on each chain. As with a myriad of five chains then an attacker would need to control three of the five AuxPoW chains to control the network.
Not being a miner, I am leaning towards Crytponight as my favorite proof-of-work algorithm. It is heavily CPU oriented, which will put off mining centralization for some time.
Perhaps there are similar cpu-oriented algorithms out there, but cryptonight addresses another important point: If we go toward merged mining in the future, which coin would we want to do this with? The only coin that I know of that is putting privacy first, and for which the developers have some integrity, is Monero. Given the new partnership between the two developers in PrivacySolutions.no, if we went in this direction, this choice seems to be a no brainer.
The only other algorithm out there I have some respect for is Peercoin's proof-of-stake (though I would prefer a 100% proof-of-stake system...). A built in inflation of ~1% is something that we could probably live with. No one would get rich mining via POS, which is fine by me. Unfortunately, I don't think that POS will work once Zerocoin is implemented. POS would probably only work with ANC balances (which can be "staked"), and not with zerocoins that are in an anonymous escrow pool. I suspect that about a third of ANC will be locked up in zerocoins, which will limit the number of people mining via POS. It is possible that I am wrong, and that zerocoins could be staked like ANC, but this would probably require some important modifications to the original algorithm, and with zerocoin development going on, combined with the arrival of scrypt asics, I don't think that we will have the time to implement this.
Going with Cryptonight Monero AuxPoW would just be handing all the newly hashed coins over to botnet 'owners'. Having a GPU friendly hashing algorithm helps to keep the botnets away to a larger extent. Vertcoin is planning on changing to the Lyra2 hashing algorithm. Which will be GPU friendly plus the Vertcoin core dev team are committed to do what it takes to avoid ASIC centralisation. Also there's soon to be Feathercoin's new NeoScrypt algo which should also be GPU friendly. Then there's Darkcoin's X11 hashing algo which is GPU biased as well. There's three GPU friendly hashing algorithms. Scrypt merged-mining with Litecoin would be the quickest and easiest solution for now to secure the network. While the myriad could be added in later.
Peercoin is interesting in that it promotes the running of full nodes through staking. Which in turn helps to avoid the dangers of the likes of Sybil attacks. Although as stated Peercoin is of course inflationary in nature with no hard cap on the total amount of coins to be issued.