Damn, I'm running Photoshop 6.0 and it starts up in about 3-4 seconds. It started up that fast on my 400 MHz K6-2 with 256 MB of RAM also.
I'm running an Athlon XP 2500+ with 768 MB PC2700 right now, and it doesn't open any faster than the K6-2.
-Lasereth