Are there algorithms that could have been chosen for mining that balance CPU/GPU? The mining algorithm for Bitcoins (and most alternative but similar currencies as well) is purely computation hard, but not decision hard or memory hard. This caused the unexpected effect that GPUs are insanely good at mining and CPUs are so bad at mining that there's almost no point in using them to mine.

This has had many effects, including the concentration of mining into specialized hardware. Suppose that I think that's bad and would prefer that commodity CPUs be optimal for mining and that mining on them be practical. Given the requirements of mining, particularly that it work like a lottery and that valid results be quickly verifiable, are there algorithms that could have been chosen that would have resulted in commodity CPUs being the optimal miners?

Are there algorithms that require lots of decisions and/or lots of memory that could serve as the mining algorithm on future crypto-currencies that would make CPU mining practical again and give everyone with a high-end CPU a reasonable chance at mining?
The scrypt key derivation function was explicitly designed to be resistant to hardware optimization, with an explicit trade-off allowed between memory and cpu usage:


  The scrypt key derivation function ... is designed to be far more secure against hardware brute-force attacks than alternative functions such as PBKDF2 or bcrypt.


This makes it better than SHA-256 or bcrypt if the intent is to give more of an advantage to CPUs.

Another option would be to include the same sort of variety of primitives that are provided for general purpose CPUs, e.g. a combination of floating point operations, access to large memories (perhaps including something that would use a large random access memory like a disk), etc.

But as Thilo point out, including some sort of anti-botnet feature might also be needed.  A CAPTCHA might also make it rather unpopular, but some sort of work load that would indeed be noticed by a regular computer user might make it hard to hide botnet activity.