8GB is probably the minimum you'd want for a smart phone depending on what type of apps you use. If your use is minimalistic and you use it as an addition to your home PC with a few apps that interface with your full fledged ones then it should be enough.
It's mostly games for now which take up 100+ MB's but I wouldn't be surprised if other apps come in such as with photo editing and movie editing where you're gonna want more space. Then we get into using it as a PMP (portable media player) which can really kill any space you have.
have you tried streaming?
I find that I like the randomness of the streaming apps. Slacker has passed Pandora as my favorite but I have both installed on my phone. Of course I keep a few playlists with 50 or so songs on each for when I know what I want to listen to.
Unfortunately all fingers point to both AT&T and Verizon, the big two, killing the unlimited plans. AT&T has already done so and Verizon has been putting hints at this for a while now. Even if they re-introduce it later, it'll be with more expensive plans. So the streaming apps may not be ideal. So the future is fuzzy on streaming apps unfortunately.
*Edited for better coherency*