I was pretty nervous about the lack of HDD space as well when making my purchase. However, the more I thought about it the more I realized majority of what I do is in the cloud. My music is all through Spotify, my documents are all on Google Docs, pictures are saved on Google+ and I don't really mess with Videos.
I just bought my 13" Air with 128GB 48 hours ago. Since then I have installed Spotify, Chrome, and Adium without intention to stall anything else aside from possibly Word and Excel. Right now I still have 105GB of space left and I really doubt I will ever get close to filling that up.
However, if you still use iTunes with your music stored on your HDD and like to save a lot of pictures/videos on the machine then you will probably run out of room real fast.
Depends on how you plan on using it I suppose.