Ditch crypt(). It's easy to use a really solid algorithm with no surprises or platform-dependencies.
Using a salt is mandatory! Without it you have essentially no security. To prevent dictionary attacks, the salt *must* be large and random. Perfect randomness is not needed -- it just needs to have enough completely random bits that two passwords are unlikely to get the same hash, and that it is infeasible to build a dictionary for all possible salts.
The hash algorithm must be cryptographically strong. MD5 is good enough for casual use, and SHA is almost certainly good enough.
You can also use any block cipher in CBC mode as the hash. Make the salt the first plaintext block, the password the next block (padded out to the full block size with untypeable characters), and the final cipher output is the hash. Twofish and Rijndael would be good.
Salt + hash prevents a single-dictionary attack, where an attacker prehashes an entire dictionary and saves the results. This forces the attacker to run through the whole dictionary for each password, which greatly increases the computational requirements. Unfortunately if the attacker gets ahold of the salts, they can do a per-password dictionary attack.
Make the per-password attack harder by doing more calculations. Instead of just hashing salt + password, use salt + large_value + password. large_value should be large enough that hashing on an top-of-the-line CPU takes a long time, say 100 milliseconds. 100 ms would take 33 minutes to try a 20,000 word dictionary. large_value should be either constant, or derived from salt using a pseudo-random number generator. Of course, it'll take *you* a lot of CPU cycles to authenticate users, and you'll have to have enough spare CPU cycles available for the job.
Using large_value isn't perfect, but it at least makes the cracker earn the password, especially if you can afford ultra-fast CPUs/custom hardware and the attacker cannot.
You should also consider doing authentication on a *really* secure machine. Choose an extremely solid OS, install as little software as possible, and lock it down as tight as possible. Your backup strategy should involve either a visit to the machine, or extremely careful use of cryptography. My personal preference would be a box running DOS or QNX or something similar, talking to the web server over a serial cable using a checksum-protected protocol, with no NIC, and with physical locks on the case and removeable-media drive. Oh, and with a large, constant delay for each authentication attempt, regardless of whether the attempt succeeds or fails. Be sure not to authenticate willy-nilly to avoid overloading the authentication box.
I don't want the world, I just want your half.