> Could you implement something like IRC's "flood prevention" in a proof-of-work based consensus algorithm -- so sending messages closer together costs prohibitively more?
This seems easily circumvented by creating lots of identities. Though maybe creating an identity could be costly?
Gold's a pretty good analogy. We're not quite to the point where it's impossible to make money mining, but you have to plan carefully to break even.
The real usefulness, though, of bitcoins/gold isn't to make money mining, but rather as a secure medium of exchange. Bitcoins are a bullion currency that you can spend online.
You can ask around in the #bitcoin-otc channel on Freenode to get an idea of who's considered reputable. I understand Bitcoin4Cash is generally well-regarded.