I got the Fire the first week of release. At first I was apprehensive about running out of storage, but that has turned out to be a non-issue for me. I have about 60 apps stored on it now and I still have about 1/3 of the space reserved for apps empty (I've had up to about 80 apps at one time with room to spare). I have about 50 books on it and a couple hundred songs on it. I use the Amazon cloud and Audiogalaxy (sideloaded) to stream the rest of my music collection.
Having said that, bear in mind that I don't store movies on it; when I want to watch video, I stream it.