I use a 16GB SD card.
My ext2 partition is 1GB, just to be safe.
I love being able to install as many apps as I want without worrying about running low on storage space.
For a 2-4GB card I would personally want around 512MB, but you should easily be able to get away with less if you keep your eye on the amount of apps you install.
SA, You never know if you will need the extra space. The other day I was doing the normal backup routine before flashing a new ROM and found I had 380MB used on my ext2 partition.
I tend to install lots of apps. No junk, just alot of things I like and need.
I would rather have extra space than run out when it's needed.