It all depends on what you will be storing on the phone. 16GB and 64GB will give you 9GB and 57GB storage for user data respectively. Your apps go to another partition so it doesn't use up this space.

The main criteria is how much music you have. Normally you'll want to keep all your music on your phone all the time. Photos, video and other media are just stored temporarily for consumption.

Allowing 2GB for video, 1 GB for other media and 1 GB spare, I would say you should be looking at 64GB if you have more than 5GB of music.