If he's likely to put movies and/or music on it, 64 or 128 is an absolute must.
If like me, he's unlikely to do either, you actually *may* be able to get away with the 16. I use mine for writing, reading, surfing the web, and a couple of games at a time--I usually have around 4-5 GB free. But most people need more storage. My husband went with the 32 when he bought his Air last year, and he's pushing up against that limit right now even without movies on it--multiple games that take up a lot of space, hasn't cleaned out his Camera Roll or excess apps in quite a while, etc. 64 would allow him to carry a few movies for travel along with all of that.