Okay... I found something that makes a difference.

I noticed my Bookmarks Toolbar was no longer visible, and I need to access those regularly. So I went to Library --> Bookmarks --> Bookmarking Tools --> View Bookmarks Toolbar.

After choosing View Bookmarks Toolbar, I chose Restart with Add-Ons Disabled and I was back to the super slow start of 30-40 seconds.

Is there any way to fix this?

Additional Note:

Hiding the Bookmarks Toolbar only made a difference in the start-up speed of Safe Mode. It did not make any difference when starting in Normal Mode with all the extensions disabled.

Still, very surprising to me that it made such a huge difference in Safe Mode start up speed. Is that normal?

More Information:

I forgot to mention earlier that I disabled Pocket, and that didn't help either.

Also, I just installed FF Quantum a few days ago after having a rather old version on my computer. (I had been using IceDragon in anticipation of the new FF being released and breaking my extensions, but then IceDragon updated a few days ago and broke them anyway... so I switched back to Firefox.)

Could it be a problem with some left behind program data from a much earlier installation? Can someone advise me how I can make sure all old program data is removed if it will be helpful to reinstall Firefox 58.0.2?

Firefox’s Safe Mode is intended for troubleshooting in order to pinpoint hardware acceleration or an add-on, including themes (!), to be the root of any issues.

Now that you know running that mode solves the speed issue, make sure to disable all extensions manually, run Firefox in normal mode and enable them one by one, then use the default theme (because a faulty other one can cause this too) and finally disable hardware acceleration only - all one at a time and in preferred order - to see when exactly the issue starts reoccurring.

So far you seem to have done all this. My gues is the Undertaking Liberty theme is the culprit, so given what you wrote, try to entirely uninstall it instead. Obviously that theme is rather old (2009!) and has few users - I wouldn’t be surprised if it can’t cope well with Quantum and higher releases. A rule of thumb: disabling add-ons rather than uninstalling - as with e.g. antivirus software - may not guarantee that software to be fully disabled.

Do note that disabling hardware acceleration requires a Firefox restart, so don’t rule that out.

You could also create a new profile and only install that particular theme when running that profile.

Thank you for your reply Tonnes. I had already tried all of that. The Undertaking Liberty theme was still showing in "Safe" mode, which was surprising (unless the Restart with Add-Ons Disabled isn't the full Safe Mode), and it ran just as fast with it as with out it in Safe Mode. (The only slow down was when Bookmarks Toolbar was shown in Safe Mode, which was weird.)

I also tried starting normally with all extensions disabled, hardware acceleration disabled, default theme with restart and it always had the same problem.

I eventually went ahead and chose to Refresh Firefox instead, and just went ahead an reapplied my theme and reinstalled all of my extensions. Firefox is now running as fast as it did in Safe Mode... so I have no explanation for why it was so slow before. (I also have my Bookmarks Toolbar visible, and it's still fast. I really don't get why that broke Safe Mode either.)

Anyway, thank you again Tonnes for taking the time to reply. I will see if I can mark this as solved in case anybody else has the same exasperating problem.