I had an iTouch 32 GB before I got my iPhone 4 16GB, and I'm here to tell you it is worth it. The iPhone 4 is so much better than the last gen iDevices. The features especially the retina display is well worth it man. I do wish I had a little bit more space sometimes, but if I had to do it all over again I'd still get the 16GB because its taught me how to manage my memory space better. But the reason I'm almost full is because I have like over 300 apps. And I have about at least 1 movie on their about half the time. But if your so worried about it just use your iPhone 3GS as a secondary, thats what I also do with my iTouch. I always keep my iPhone in my left pocket and my iTouch in my right pocket. Hope this helps.
There are some significant improvements made in the iPhone 4. However, it depends on your usage needs. How many gigs are you using now? If it is significantly less than 16g, then it would make sense to switch... If not, then maybe you can stick with the 3GS until a better deal comes along.