I'm not really sure what made this suddenly appear, but I've noticed over the past few days that my initial connections to websites have started taking longer and longer. Today, it became painful as the browser would say it was "Looking up example.com" for a good 3-4 seconds (if not longer) before loading the page. Once the lookup completed, the site usually came down pretty fast. Thanks to a (not so quick) Google search, I ran across this forum thread. It turns out, disabling IPv6 in OS X speeds things up quite a bit. To disable, go to System Preferences -> select the network interface you're using (probably Airport) -> click Advanced.
Then, in the TCP/IP tab, change the drop down next to "Configure IPv6" to "Off" instead of "Automatic".
This worked for me. My browser and other various apps no longer take several seconds before loading pages on the web!