WPA-PSK uses the name of the network as a salt. There exists rainbow tables for millions of passwords for many of the most used network names.
It doesn't really have to be random, just not something widely in use. In other words, just don't leave it as "linksys", I'm pretty sure that even a 13-char random string doesn't help you then. :)
No. The ssid is used as part of the encryption. Changing it to something very obscure invalidates any precomputed tables and forces a brute force attack