"Software update failed. An error occurred downloading iOS 9" - weird message after clicking 'Download and install'. Restarting devices didn't help. What's the problem?
iOS 9 just came out and since many are trying to update to it, it seems like a server overload on Apple's part, this article from 9to5Mac also confirms this. Unfortunately, all you can do is be patient. I still only see the iOS 8.4.1 update available on my iPhone 5S.
Golden Rule - don't do the Download & Install at the same time.
Hit "Download only" when iTunes asks you. Saves a lot of heartache in the long run.
It ought to go without saying that you should both sync & backup to iTunes before doing any upgrade.
One very smart thing to do before trying to long-haul any large file is to reboot all your network hardware; modem, router, puter etc.
I got my update first try, but I couldn't for the life of me persuade it to login to iCloud. Power-cycling my WiFi [which had been running for months since its last cycle] simply 'fixed it'.
As with anything so vague as 'switch it off then on again' - YMMV.
Another easy fix is to insure there is enough memory remaining. I had to delete or transfer a lot of photos, videos, music, etc. to get back enough space to download the new iOS.