I installed an additional 128 MB of memory in my computer and now it seems like it takes much longer for the computer to startup after shutdown. Is there some correlation between the amount of memory installed and startup times?

Yes, the memory test is part of the startup routine for computers introduced after mid-1999 such as the Power Mac G4, PowerBook G3 Series (FireWire), and iBook. Having more memory installed will extend the amount of time it takes the computer to boot.

Disabling the startup memory test may help reduce long boot times if you have a higher memory configuration.

Note: This option is normally hidden until you press and hold the Command and Option keys while opening the Memory control panel. The startup memory tests are designed to ensure that the memory is fully functional in the computer. You should disable the startup memory tests only if you are experiencing a long delay in starting up your computer.

Additionally, ensure that you have highlighted a startup disk in the Startup Disk control panel. Not having a disk highlighted can extend the startup time.