I have the 16G iPhone4 and I'm not someone who puts his entire collection of songs onto the device (which won't fit my 60GB+ of songs anyways). I have 70+ Apps (<2GB) for the 2 months I've owned the phone so far and a minimal amount of songs (about 1GB) and about 1GB of pics/vids and I still have 10GB free. The iphone 4 takes HD videos at a decent bitrate (about 8-10Mbps) so if you like to take vids and keep all of them on the phone drive space may be important. I don't forsee needing more than 8GB of space to keep my pics/vids in the phone all the time and not syncing back to iTunes. Apps don't take up that much space except perhaps Nav app (which I don't have one and I assume at most 1-2GB of offline maps top). Next drive-space hogging apps are probably the 3D-intensive games (100s of MB each is not uncommon). Most other apps take very little space.
If my 16G phone ever gets close to full capacity I'll just remove the less-frequently used apps from the phone (but leave them in iTunes). One note of suggestion is to sync your apps on the phone to iTunes often. Apparently, apps hog up drive space over time. A few times I've seen the drive space usage goes down after syncing to iTunes, even though I didn't instruct to remove anything from the phone. In an extreme case, my sis-in-law disable the option in iTunes to sync apps from Day 1. By the time she needed to upgrade iOS to v4.1 2 years later, iTunes failed because it showed her apps taking up all her drive space in the phone although she only had about 2GB-worth of 100 apps.