Artwork
Hi,
I had the same issue. In my case syncing 2 phones, a 3gs and a 4 from same mac/same itunes/both 128 option/same everything. The 3gs had 5gb more free space than the 4.
I downloaded a tool to mount the iPhones as disks and had a look at the contents, and the only difference in size is the artwork folders. I later confirmed this w/ applecare. After they escalated a couple of levels to figure this out (did all the normal restores etc), they confirmed that on the old iPhones the artwork is scaled down, but on the 4 it's left at a higher resolution (since the screen has better resolution).
Note: you can confirm that it's not the music files, if you expand the iphone in the iTunes device list and click on music. In my case it shows approx 19GB there, but on the audio capacity bar it showed 25GB. The difference is that audio capacity bar shows music, ringtones and artwork.
Guess only option is to either remove the artwork, or hope that apple adds an option to have "low" quality artwork on the iPhone 4.