disclaimer: I’m not a cryptographer, but I think I understand some of the basics of it.
With a rainbowtable, you basically precompute all possible hashes for a specific hash function and a specific range of paswords (character set and maximum length). It can work with any hash/one way function. Once you have this table, you can easily look up any hash value and read out the accompanying plaintext. The smart part of rainbowtables is in storing the tables in a very smart way that requires only gigabytes instead of terra/exabytes. Generating these tables is more-or-less equivalent to doing a brute force search of the range of passwords. The size of the table is, I believe, more-or-less proportional to the ‘password space’, the number of possible passwords there are within your charset and max length, and it also depends on the ‘accuracy’ of the table. (Read Jeffs previous post about them, it says each table can reverse xx percent of hashes of passwords within the range. Rainbowtables use probablistic methods.) (Although some math on the numbers on the rainbowcrack site show the relation password space - table size isn’t really proportional, so I’m probably saying some things about stuff I don’t actually know enough about.)
Rainbow tables work equally well against any kind of hash function, be it SHA or rot13 (though with rot13 there are other, easier ways to ‘crack’ it). The only factor is if the tables for a specific hash function already exist, or still have to be generated. (Assuming nobody has gone through the trouble of building a rot13 rainbowtable, rot13 is actually /more/ secure against rainbow crackers than md5 or SHA.)
Since md5, sha, windows hashing scheme and the like are well known hash functions, the tables for those can be found for free on the net.
Using a salt with your hashing function, you basically create your own private hashing function, for which new tables will need to be generated.
Generating rainbowtables is fairly expensive, but as the worlds largest supercomputers are botnets, I wouldn’t assume determined crackers won’t do this if the information in the stolen databases is valuable enough, though the bar is quite high. (And, as far as I understand rainbowtables, its very well possible to parrallelize rainbowtable attacks.)
Users passwords are often not very complex, a dictionary attack will find a large percentage of passwords. Salts can be made as complex as you want, by just using a longer string of randomly generated characters. When using a global salt of sufficient complexity, an attacker will have to get to that salt as well, because it won’t be feasible to do a brute force/rainbowtable attack on the database without it. If the attacker has access to the salt, he can then generate a new rainbowtable for the compromised database with the hash function + salt, and once he has done that, he can compromise basically all passwords in the database. (But building the table is at least as expensive as doing a brute force search against the database.)
Using a different salt for each password (which then has to be stored alongside the password) basically makes it harder to generate the rainbowtable, because the attacker now has to combine each attempted password with each of the hash values found in the database. I’m not quite sure if it will be as expensive as doing an individual brute force search against every entry in the database separately. Also, if you only use a global salt, the attacker can start generating the rainbowtable once he has that salt, but before he has the database, and then use it on any user account.
So, AFAIK, the most secure way is to use both a global salt and per-user salts, and keep your global salt stored separately from the database, so an attacker won’t easily get to both of them. Though having just one kind of salt already keeps you safe from an atacker who can’t generate a new rainbowtable.
Of couse, once an attacker has both the database and the salts, the most important thing standing between him and your password is your password’s complexity, so use strong passwords!