I have a 32GB and don't regret it. I have about 8-9GB left. I figured $100 extra is worthwhile over the period I keep my phone. I had an 8GB iPod touch prior to my iPhone and never thought I would need more than that - And I don't, but now I just have better options (which I like).
Plus, if you sell your iPhone later, the 32GB will fetch for more than a 16GB would, so in the long run, you aren't paying a full $100 more for twice the space. After you sell it, you might be paying $30-60 for twice the space (32Gb iPhone 3gs sells for 300-320 on ebay ... but a 16GB sells for $250 - 270 on average)
OP, i have the same predicament as you. i got the 16gb 3 days ago and i'm thinking of exchanging it for a 32... i guess i still have a few more days to decide.
32gb basically means i can bring all my music with me. On my ipad 64 gb basically means all my music plus a bunch of movies or tv shows.
It is a lot of space but i am sure you will find a way to use it up.
i guess its just that feeling that u can put more crap on your phone. i absolutely love my iphone and the only other phone i would get is the iphone 5. i see paying $100 for 32GB might be good for 2 reasons
1. extra memory for only $100 more
2. will sell or trade in for more money if i decide i want the iphone 5