I have a PB G4 1.5Ghz with 1.5Gb RAM and about 3-4 months ago started having lots of problems with lag/beachballs. I would consider myself a real basic user (Safari, Office, etc.), so I have no clue what is causing it.
It started happening right about the time I did an upgrade on Office (from the Microsoft AutoUpdater). If I restart, everything is fine for a few days and then I have to restart again.
Not trying to bash Microsoft, but it may be Office that is causing the problem...did you do the update as well?
No Office installed here and it is still really slow.