I've owned an iBook G4 1.42GHz and now a MBP 15" 2.8 GHz.
My experiences for both have been the same.
First boot, obviously takes time as it runs through the intro video, etc.
With no user accounts and no wireless settings, it is then quick.
Once you add a couple of user accounts and set up networking, inc wireless, it slows it slightly.
Then mine is more or less consistent. The only time it slows is when a system update has been installed. For a lot of these it needs to do some re-configuring so will be slow on initial boot, but returns to normal after that.
As stated in other posts, the only thing that woud slow a Mac down is if applications are loading background processes when you power up your mac.
Goto system preferences, user accounts and the login items tab to see what OS X is loading on startup. This list is not thorough though as some processes don't follow this protocol and you might need a 3rd party app to expose.
Keeping an eye on what processes are running is useful though, especially if they are consuming a lot of processor cycles or memory.
It looks like Snow Leopard will be a lot quicker to boot.
My final comment is that my MacBook Pro boot up and lets me open up firefox about twice as quick as any PC I have used!
Phil