Short version (you almost got around to it, but didn't explicitly state it :)) -- Don't use straight hash functions because they are made to be fast. Even if you salt/nonce them, you can generate private rainbow tables quickly.

Use a password hiding method that's slow to compute (slow being "this operation isn't implemented in hardware or optimized assembly") which is what bcrypt or scrypt provides.

Differences in speed/effort are mentioned at http://www.tarsnap.com/scrypt.html -- scrypt enc is approximately 100 billion times more than the cost of cracking the same password on a file encrypted by openssl enc