Since the problem has been growing, my first suspect would be hard drive trouble. Have you defragmented lately?

Another possibility is a corrupted preferences file. To recreate the preferences, hold down ctrl-alt-shift while launching Photoshop.

I can't think of anything else that would creep up on you gradually like that, but I do know that the new OpenGL acceleration has been known to cause significant slowdowns. That can be turned off in Edit > Preferences > Performance.