Firefox 3 made some improvements by moving the browser history, bookmarks, etc. to an SQLite database. It also changed the default settings to keep history information for a longer period of time. Regular use causes the the places.sqlite file to get fragmented and bloated, and slows down Firefox’s performance.
This problem is easily solved by periodically “vacuuming” the places.sqlite database. You can do this manually via the directions in this Lifehacker article. Alternatively, the Firefox extension in the linked article provides a status bar icon to do the job, and also allows you to set up automatic defragmentation. Note that the extension only works for Firefox 3.5 or later.