Im soooo Glad almost everyone is saying 32GB, this way I have an easier time getting the 16GB version.
Im not big on apps, and I only really use my storage for music and pictures taken with the iphone.
So 16GB is fine for me.
Edit: Also until Apple allows for you to drag and drop files (movies), I personally have no need for more than 16GB. I ifnd it too cumbersome using itunes for Movies.
Handbrake is your friend. It's free and stupid simple to use. Just encode and add the file to iTunes. Not way that is cumbersome.
I agree Handbrake is great. Another option which means you don't have to wait for the conversion to complete is to get an app like VLC. That is my preferred option now.