I had problems where I'd type 'f' and it would take a good 10-15 seconds to give me suggestions/previous browser visits.
https://addons.mozilla.org/en-US/firefox/addon/13878 fixed that problem. Apparently, Firefox uses SQLite to store stuff, and rather than deleting old rows, it just marks them as 'deleted' so the file gets huge and bloated.
This purges the old ones. Defragments it and makes it awesome!