Bitcoin Q&A: Public Keys vs. Addresses

What is the difference between public keys and addresses? How are new addresses generated? How are change addresses generated? Why have two outputs? Do you still pay fees if you are sending bitcoin to new addresses in your own wallet? What is the VanityGen command? What does the SIG_HASH flag do?