Tried upgrading, then did clean install (x2)
Initially I did upgrades on the Macbook (2.16 C2D) and iMac (2.8 C2D) and it was kind of okay but several beachball episodes while running software like Safari, iTunes, iPhoto, nothing really complex.
After a week or so I decided to try an clean install on the Macbook and what a difference! The machine absolutely flies now. That was a month or more ago, and it's still perfect. I never thought that a 2.5-year-old laptop could work this well.
Based on that, I did a clean install on the iMac too, which is also working beautifully—not such a noticeable difference as on the Macbook, but it definitely (subjectively) is much smoother and faster now.
(Faster as in UI interaction; I can't imagine that any processor etc. benchmarks would show a difference).
I'd say a clean install is definitely worth a try if you think you have any problems.
(Note that mine were properly clean installs, involving re-installing Apps and re-creating preferences, just dragging across the Documents folder from my Time Machine backup - I didn't want to take chances with a 'Time Machine Restore' of anything that might potentially be causing problems).