All bookmarks, history etc. are in the places database. This can get fragmented over time, slowing things down. Fix this by:
1. Opening tools > error console
2. Paste Components.classes["@mozilla.org/browser/nav-history-service;1"].getService(Components.interfaces.nsPIPlacesDatabase).DBConnection.executeSimpleSQL("VACUUM");
3. Press enter.
The interface may freeze up for a little bit, but things should run faster