The iPhone OS 3.0 update took

Before I began the update my 16GB iPhone had 3.82GB available space.
iTunes backed up my current iPhone (which I had already done manually so it was pretty quick).
iTunes contacted the iPhone activation server to be sure I had the real deal.

The activation server seemed stalled for almost 45 minutes. I gave up and told iTunes to quit via the Dock and that seemed to goose the thing into action. The  “Contacting activation server…” modal window went away immediately, the phone rebooted and a new modal window “Waiting for iPhone” took its place.

Soon that was replaced with an “Updating iPhone software…” modal window with progress bar. The actual software update and verification took about six minutes from beginning until the phone rebooted.