For Firefox users, I recently did the following: follow the instructions here http://forums.mozillazine.org/viewtopic.php?p=8494865&sid=37... and run SpeedyFox, which on Mac is I think just a SQLite cleanup tool.
But, it made a huge difference. Deleting all of my history older than six months pegged one of my CPUs and made FF unusable for about 20 minutes, but that, deleting all my cookies, clearing the recent download list, removing a couple of rarely/never used addons, and running SpeedyFox seems to have helped a lot. So speedy now.