I have the 128 and have never felt a lack of memory. As a matter of fact, I split it 50/50 with Windows using 60GB and Mac using 60GB and I still have like 30GB left on both partitions.
Just make sure you have an external hard drive for music and pics and other wasteful space huggers and you're good to go!
Not everyone can fit their os and applications into 60 GB. I would even struggle with 128 GB so I can't see how anyone here can offer advice of xxx is enough for me, therefore it will be enough for you.