Firefox has taken longer to start with each version as well, In my experience.
Also, IE6 did not start faster or run faster thant IE 5.5, in my experience. There was no discernable difference. And if there was, I imagine it was because Trident was updated to support the draft CSS2 specifications, which IE 5.5 only sorta kinda pretended to do. IE5 certainly wasn't faster than IE4 by any margin.
Each new version of the software took advantage of features in newer Operating Systems.
IE1,2, and 3 were designed for windows 3.1; each one required more memory and more processing power, because they each did more. Running IE3 with the same specs as IE1, IE3 would run slower.
IE4 was first released as part of Windows 95, as well as being a requisite component of a number of other applications that used InfoViewer (Visual Studio 6, for example). It was, again, slower than IE3, because it now supported a *censored* of a lot more; javascript, java, applets, COM components, ActiveX controls, etc. And, naturally, the change from a crappy toolbar to a ReBar/CoolBar control. Anybody saying IE4 is faster than IE3 clearly hasn't used both.
Each new Version basically made it's debut on a new OS release; IE4 on Win95, IE5 with Windows 2000, and IE6 with Windows XP. each of these operating systems had their own differing requirements and the time period between the releases of the two operating systems meant that faster hardware was a lot more accessible, and usually a given with the new Operating System. The requirements for windows 2000 and Windows XP were the type of system that nobody could even imagine running Windows 95 on at the time of it's release. Comparing how IE4 runs on a Windows 95 machine with Windows 95-average specifications with IE6 running on an XP machine with "Standard" XP-era specifications is a biassed comparison. All you are saying is that "software runs faster when the computer is faster" which is obvious and it says nothing about the relative speeds of the software in question.