FINALLY! I MAY HAVE SOLVED IT!! Fingers crossed, but I may have finally fixed my issue. I couldn't seem to get my iPhone 6S to backup no matter what. I wish I had thought of the solution before I went through this nightmare ordeal over the last few weeks. I had tried everything, and yes, I do mean everything. Deleted the backup, tried unselecting all apps hoping it was some corrupted app data, , tried a different wifi network, turned off backup and turned it back on, signed in and out of iCloud, reset my phone, wiped my phone and restored from iTunes backup, wiped my phone and started from new. I thought it was weird that even a fresh install in which all I did was sign into iCloud then hit Backup didn't even work. I even went way farther than these troubleshooting steps and deleted all app data in my iCloud except for my iCloud Photo Library and some successful backups from other devices. I also removed any traces of my phone from my iCloud by going into my AppleID management and removing it from the list and removing it as a trusted device. Except for the photos and the other backups, I essentially nuked my iCloud. I even went so far as to nuke my phone by doing a full DFU restore to make sure there wasn't something that was getting left behind during restore. None of this worked. If a DFU restore didn't work, then it HAS to be server side. DFU restore would be like having a brand new phone.
During my extensive testing and work, (and I do mean extensive. I've spent easily 100+ hours over the last month and a half trying to figure this out doing research and trying anything I could think of.) I noticed something strange. Whenever I would wipe the phone and go through the set up, whenever I would go to my iCloud section the first time, it would ask me to put in my password again to verify it. Thought it was very weird to do that for a fresh install, so I thought that maybe there was something wrong with my iCloud account and maybe the password key on the servers. I decided to go ahead and change my password. My previous password met the requirements, so I know that wasn't an issue. Either way, I changed my iCloud password and then signed out on my 6S and then reset my phone. I wanted to clear out anything left over. I powered it back on and signed into iCloud with the new password. I went and tried a manual iCloud backup, and voila! It worked!!! I have tried it a subsequent two times and it completed successfully each time. I am in the process of restoring a stripped down iTunes backup that only contains my Watch data, Activity data, messages, and voicemails. I may try restoring a full backup later if this one works. If you've tried everything else and still have issues, try changing your iCloud password. 6 weeks in and I finally seem to be able to back up. I am currently backing up my phone from that stripped down restore and it is actually telling me how much time it has left. Typically, it wouldn't even say that. I will come back and update whether it was successful or not. Pray with me that this ordeal is done. If successful, I'll pass this information along to Apple support so they can figure out where the issue was.