There is another interesting idea buried in there: switch from a "lottery" to a "raffle" (their terminology). Or in more standard terms - change from a winner takes all distribution of rewards to a proportional distribution: everybody who mines the next block in the chain get some reward.

I did not see any ideas for how this could be implemented, but it could remove a drive towards centralisation from the current blockchain approach.

Don't mining pools do this already to some extent?

They do; but the proposed system would do the same thing in an entirely non-centralized way.

This would be a good thing because as it is now, there are multi-coins pools that will switch their users' hashing power to other chains depending on how profitable coins are. The concern is that large mining pools have a lot of combined hashing power and some dishonest ones could consider switching that power to specific coins not based on the revenue potential but for other reasons (51% attacks and the like).

What I'd love to see (don't know if this has been explored to some extent yet) would be proof of work but for useful work: think Folding@home or Einstein@home (BOINC stuff in general) in order to mine a blockchain.

It's very hard to do (if it is even possible) in a non-centralized way though. Who submits the work ? who validates it has been performed properly ? and so on.

The http://www.truthcoin.info/blog/pow-cheapest link given above explains why you can incentivise useful processing but it won't stop the 'waste' issue.

You also have the problem of regulating the difficulty if you want consistent rewards. Non-pure math problems aren't going to allow that.

This is Ethereum: "Mining" generates Ethers, but also runs code, potentially powering useful blockchain apps.

The current PoW algorithm in ethereum is ethash and does not perform useful work during coin generation, unless I'm mistaken. You spend ether to fuel useful work.

Also, Ethereum (forked) aim to switch to PoS soon (ETC may not).

Of course you are right, coin generation is a waste. The part where ether is changing hands for useful work is at least somewhat "useful".

Best we can hope for is a future blockchain that emphasizes this kind of work more. A seti@home-coin or cure-cancer-coin is, as you suggested, hard to implement.