So as I've described in my question, it was during the "cleanup" process when my computer powered down - albeit gracefully, dnf didn't take it too well.
The cleanup stage removes old packages from the system, as the new ones are already installed. This is kind of a problem, when trying to do a dnf distro-sync. While it will fix package clashes, it won't downgrade some of the packages.
My system - or more specifically dnf was still assuming it's on Fedora 22, which it kinda is and is not at the same time; but the fact that it thinks that, is quite helpful.
Because the newer packages are already installed and some of the old ones delted, it makes more sense to push to the newer release, as Fedora 22 was already missing packages (since update was already cleaning up).
when running dnf distro-sync --releasever=23 you'll run into dnf not wanting to uninstall some of the (new) packages, because they're protected.
This problem can be somewhat easily circumvented, with dnf distro-sync --disableplugin=protected_packages --releasever=23. The reason for that is, that some of the allready installed fc23-packages are already there and protected (one of which, is dnf itself, for example). But the old fc22 package of dnf hadn't been cleaned up yet. It's still installed and protected.
Since the upgrade process was halted pretty much mid-removing the old files, there are numerous version clashes between the fc22 and fc23 versions, respectively.
Some of these clashes can be circumvented by using an additional --allowerasing switch, which helped a little. In the end though, I had to remove most of the clashes myself, which meant going package-by-package and removing the problematic ones.
I ended up removing all texlive-* packages before moving on, it sped up the process of upgrading - failure - retrying, and made going through installed packages much easier.
Eventually, a dnf upgrade --refresh --releasever=23 --allowerasing installed a bunch of upgrades and pointed me to the few remaining version errors. After that, booting into Fedora 23 was no problem.
It should be noted, that the solution would be somewhat different, if I was in the "installation"/"upgrading" stage of the process, when the power fail occurred. I'd have probably distro-synced back to Fedora 22, removed all the fc23 packages and started anew.
dnfwas in the "cleanup" stage. I'm working on a contingency solution right now.