Also what restore are you talking about? restore to factory settings? restore from a recent backup? restore from a custom firmware?
the longest will be restore from a recent backup since it will restore all your data like sargd66 said. The time for that also depends on your data, if you have a 32GB 3Gs with 20GB of data then it will take quite awhile compared to a 16GB 3Gs with 8GB or data.