Please do not go with a Zune.
I was originally confused, because I unsure if you were asking how much memory you needed on the iPod or how much memory your computer needed for the iPod.
It seems you were asking about the memory on the iPod, and in that case, I agree with all previous answers (besides the Zune).