Does it effectively output a single binary?

Yes, that's one of the points of NativeAOT, a self-contained single binary, exactly as Go does it.

Does it create some kind of clusterf*k and awkward packaging formats like other MS solutions such as UWP?

No, you can create .exe files.

Will it actually be deployable to a random fresh install of Debian 12 or Windows 10?

Yes, NativeAOT supports Windows, Linux and MacOS, x64 and Arm64.

What about compatibility with older systems?

Not sure about that, I suppose it depends on the targets each .NET version support. For example, .NET 8 will drop RHEL 7 and only RHEL 8 and later.

And to play devil's advocate: this won't work for all existing .NET applications. If you use reflection (which is AOT unfriendly), chances are that you will have to rework a ton of stuff in order to get to a point where NativeAOT works. There's a middle solution though, called ReadyToRun, which has some advantages compared to running fully with the JIT compiler.