Booting from such a flash drive does take awhile, but I have no good answer to the format time. Did you do a low level format? sounds like it. Takes a long time for a 16gb flash drive to zero.
Formatting the drive wasn't the time consumer. I don't recall the time used but choosing the one partition and formatting GUID was only a matter of minutes.
The actual system install took all the time and it was done having booted from the Snow Leopard disk.
ryck