Those of you seeing "other" those are corruptions from apps or apps themselves and will take up that space unless you do one of the two options
"Other" is most typically TXT and iMessage Data and most of that kind of data are pictures and movies sent or received via TXT or iMessage.
I don't know about anyone else but some of that I consider valuable data. So if your gonna setup as "NEW", that data will be lost unless you painstaking go back through your messages and save the media files to you Camera Roll and then export them off your phone. But then you lose the "context" of the conversations related to those media files as you won't have the words or txt conversations they are apart of.
I always:
1) Clean unnecessary data off the old phone
2) Backup the old phone to iCloud
3) Upgrade the old phone to the new iOS version
4) Backup the old phone to iCloud again
5) Reset/Wipe/DFU the old phone
6) Restore the new phone from iCloud backup
7) Clean and sell the old phone
Also, considering I like to keep all my txt history I have had to increase
my iCloud storage plan and pay for it. To me, it's worth it.