I actually didn't have that much of a problem with 512mb. If all you're going to do is surf the web, use basic office applications, and have a few songs, then 512mb should be OK.
However, I only put on my huge iTunes library and iPhoto and other big apps after I put 2GB in, so I never really pushed 512mb to the limits. I'm also quite good at actually closing apps when I've finished with them (that's what being a Windows user does to you). Even with 2GB I still get the beachball for a couple of seconds when I load up iTunes.