初めまして。
先日、Firefox 36.0に更新したのですが、そこからFirefox自体の起動が遅くなりました。
具体的にはショートカット等からFirefoxを起動すると起動までに20秒程かかります。

既にFirefoxが起動済の状態だと、もう1つウィンドウを起動してもすぐに開きます。
しかし、いちから起動する場合は時間がかかります。
また、他のブラウザやアプリケーションは問題なくスムーズに起動します。
更新前までは何のストレスも無く動いていたのが、更新してから遅くなったので、このバージョンの不具合なのかと思い質問させて頂きました。
他に同様の事例を見つける事が出来なかったので、自分の環境だけなのかと少し心配なのですが、何か思い当たる事があればご教示ください。

尚、PCのスペックは以下の通りです。
CPU: Intel(R) Core(TM) i7-2700K CPU @ 3.50GHz (8 CPUs), 3.8GHz
Memory: 16GB
OS: Windows 8.1 Pro 64-bit (6.3, Build 9600) (9600.winblue_r7.150109-2022)

_________________
Mozilla/5.0 (Windows NT 6.3; WOW64; rv:36.0) Gecko/20100101 Firefox/36.0

PCのリブート直後の最初の起動だと時間がかかるが二回目の起動は問題ない、というようなのとは、ちょっと違うみたいですね。
これだと、モジュールのロード時に、Disk Cacheにあるかないかで起動時間が変わる、というだけですから。
よくあるのがアドオンのせい。
PCのリブート直後ではなくてFirefoxを何度か起動し直した後で、新規プロファィルの時、-safe-modeの時、普通に立ち上げた時で、起動時間がどのように変りますか？