I have a 16GB iPhone and only have 5GBish left, it very easy to use all the space, I have only synched some of my playlists, (34 on the phone), a bunch of TV shows and a couple of movies.
But still find use for my classic, I rip my CDs using EAC and encode them with LAME so the file sizes are much bigger then a normal mp3 but the sound quality is so much better. I use my classic in the car where it just goes in the glove box and I have my whole collection with me so I can just put it on shuffle and listen to music that is not in my play lists. And also it be used as a portable HDD which is great for carrying around lots of files, ie more videos to watch on night shift at work.
A 128 Touch would be great but at a reasonable price as the current 32GB was just to expensive for me.