While proofs of work are wasteful, the only alternative I know of is simply entrusting some third party with control of the network.
Now, this gets to the real issue: We need a source for these magic numbers, it needs to be trusted and available and verifiable by everyone, and it needs to be unpredictable and unknowable until a specific time.
What possible sources are there? You could imagine a centralized system, where some computer on the internet spits out a random number for the next 'magic key' every minute. But of course, you have to trust the owner of this computer and so we'd lose all the decentralized features of Bitcoin.
Another possibility: Tie the magic key to some public knowledge, e.g. the value of the NASDAQ at a specific time. Again, this still has problems as 1) there's a limited range of possible values, so miners could pre-compute various versions, and 2) the value could be gamed by market traders.
Anyway, I don't have an answer for the ideal source of these 'magic keys', but if someone could come up with one, you could keep all of bitcoin's mechanisms while vastly reducing its energy waste
This would seem to lead to a situation where, after a proof-of-work block is minted, those minting POW blocks relax and those minting POS blocks march things forward for each of their accounts until they find the earliest time that satisfies any of them - at which point they simply wait until that time arrives (for themselves or anyone else playing).
I have a suggestion for how to deal with these magic numbers. Make 9 out of 10 blocks duds (and it should be known in advance which), that contain very little reward. This means that, most mining power will switch of for these blocks, and only be active for the other 1 of 10 blocks.
You just answered your own question on why bitcoin was deliberately made difficult. Security and fairness.
There has yet to be a proposal that has come close to offering a better solution without massive exploitable flaws.
In an ideal world, imagine instead a variant of bitcoin that works like this:
* All miners do their hashing & number crunching for a second or so, then report their peak hashing rates to each other.
* Instead of one of them randomly mining the next block of bitcoin, the next block gets divided out proportionately according to hash rate.
* All miners then agree not to do any more hashing for (say) a minute or so.
* Process repeats.
Ta-da! We have a bitcoin system which uses a fraction of the electricity. If we were back in the days of mining on general purpose computers, then we could even put them to some other use at the same time as mining bitcoins.
Obviously, this has massive flaws. How to trust that everyone doesn't lie about their hash rates? Perhaps this could be solved by keeping the mining but setting the difficulty so that a block would only take a couple of seconds to mine. That way, there's still a numeric problem that requires real CPU work to solve.
Secondly, how to ensure that the systems don't do any more hashing for a fixed time? Perhaps the system could be tied to an unguessable source of randomness that won't be known in advance of the next block mining time. (This is the really tricky bit; you need a source that is trusted by everyone and not predictable or alterable or knowable in advance).