This is a very subjective question. All I can say is 16GB is enough for me. But 2 months later, I may say not enough. Therefore, please list down what you will do and store in the phone.

e.g. Store 5 hours movie in 720p format. Store 5 hours of music in 128k bit rate. etc.

It is the same ask asking, is Seagate 7200.11 500GB SATA sufficient ? Or should I get 1TB ?

if you're gonna use you're iphone 4 to take pictures and videos occasionally then you should get a 32gb, because HD and 5MP will use up quite an amount of space.

or you can get a 16gb but have an external HDD for backup, but that beats the purpose of having an efficient smart phone where you won't need to store stuff in your pc often.