I have also been experiencing momentary periods of sluggish performance on very basic tasks the last couple of months. I am running the latest version of Leopard and I have Time Machine using an external USB hard drive. Whenever I go for several days without letting Time Machine connect to its drive, it gets a bit sluggish with basic tasks like Finder and what not. I have about 40GB of space free on my hard disk which is more then enough to work with.
I usually draw the line at 20GB of free space on all my machines. Once I reach this point, I either clean out all the junk or I upgrade.
Also file indexing for spotlight is very expensive on memory utilization and processing power as it is a very complex data structure in memory which is continuously updated and optimized while you do your thing. The same goes for the QuickLook feature in OS X.
I never reset any of my PRAM or NVRAM (I think I did it once in almost 1.5 years).
I have done my best to investigate this particular problem over the last couple of months when time permits and I have conclude, so far, that I should just accept it as the features that are slowing things down (nothing significant mind you) are well worth it.
EDIT: Also I find the longer my machine has been running, the snappier things get which is a strong point of OS X's memory utilization algorithms.