My iPhone 3G 16 GB (filled with approx. 9 GB) via MBP/OS X needed 5.5 (in words: five point five) hours from hitting "Update" to "Software Version 4.0" in iTunes. The download itself was fast, a few minutes.
And it's very dangerous because it is not clearly determined by OS when the update is really finished. Some people disconnected the iPhone when the "Restoring Backup…" progress bar vanished finally. Yes, you can start the iPhone then, but it's in Vanilla mode only (without previous settings, apps…).
When "Restoring Backup…" has finished there are additionally two or three progress bars (Music, Videos, Apps) and one or two complete reboots of iPhone. Wait until "Software Version 4.0" appears in iTunes "iPhone" overview main page. Apple should make that clearer.
There were hints that you should disconnect all other USB devices for a quicker OS 4 update. I had my eyeTV USB receiver connected but the app war closed.