For most people 16GB should be fine as long as you put your messages, pics, video and music on your SD card. Which also has the added benefit of being independent of your core OS so if you update/reload Android and something goes wrong you don't lose them.
I have the 32GB version and have about 19GB free right now, and a bunch of stuff on a 32GB MicroSD card.