Mat, your feeling is correct. Older versions of TenFourFox were faster at start-up, but more recent versions are faster at displaying websites. It's not a bad trade-off since you only start the browser once per session.
That said, make sure you're only running add-ons/extensions you really need. Extensions may use a lot of memory and can slow down the browser at start-up and while running. Also make sure you have enough RAM installed (1 GB or more recommended). An ancient 4200 RPM spinning harddisk won't contribute much to fast start-up times of applications, either.
My personal experience: The most recent version of TenFourFox takes about 20 seconds (my default user profile with a lot of add-ons) resp. 12 seconds (with a fresh user profile) to be completely useabe after start-up on my 10.5 PowerBook G4 1.67 GHz with an mSATA SSD and 2 GB RAM. It takes about 50 seconds on my 10.4 400 MHz G3 Pismo PowerBook with 1 GB RAM and a 5400 RPM spinning HD. ('Completely useable' means that CPU activity in Activity Monitor for the browser goes down to the normal 1-3% idle value when start-up is complete.)
I can access our Sourceforge downloads with Safari 4.1.3 on Mac OS X 10.4. resp. Safari 5.0.2 (with Leopard WebKit) on Mac OS X 10.5. If your're still running Safari 3, you'll have to update Safari first.
So, I have to tell, that it is not TFFs problem. I had an Addblocker and Noscript installed, and these are the ones slowing down startup so heavy. I started to "investigate" again when I setup a Quad G5 2,5 this week with 10.4 and it also needed more than 30 seconds for starting TFF.
So I recognized that the addons are the main showstoppers. Now with using just uBlock (tried previously and kicked; "AdBlock Plus", "Adblock for Firefox", "AdBlocker Ultimate") TFF startup is back at about 7 seconds at the G5! ;)
About getting TFF; the Safari 4.1 update for 10.4 cannot be downloaded with Safari 3.x. So you need TFF for downloading it. But you cannot get TFF with Safari 3.x as well, ... still a not so funny situation, when you got no other more modern computer around. Perhaps it could be put for "emergencys" to a simple html page anywhere?