8 GB has been fine, but I wouldn't complain if I had 16 GB. I've got 3.35 GB of music (658 songs), 3 full length movies, about 300 MB of photos (which is a lot considering that the iPhone compresses the images) and I've still got about 2 GB left. At one point, I had about the same amount of music and all 10 episodes of Band of Brothers on my iPhone, and I still had a few hundred MB left. 8 GB means that you have to think about which songs, photos and movies you really want to carry around, but it's not that bad at all.
--DotComCTO