Thanks for the new firmware link, I wish I could say it fixed the problem, but alas, no luck - I was able to replicate the bug after upgrading...
You're right, AirPrint is not the best way to fully utilize a printer on a Mac, although it is what macOS tried to use as default, so I guess I'm trying to save future Xerox Phaser 3260 buyers some frustration.
As far as iOS devices go, Secure AirPrint "just works" ;) - that makes me think the problem is more likely macOS Sierra related.
Nevertheless, I will be reporting the evident bug to both interested parties.
Btw. If you ever configuring a new printer and need to print out a lot of random pages to test the install, I found that paper air plane models make for a much more fun test pages... http://www.funpaperairplanes.com :D
I would report to both Apple and Xerox actually, it would appear they added something in the public 10.12.4 release that was not there in the beta 8 release of the same OS because it worked when I tried it a few weeks ago, so it would appear Xerox has not come across the new implementation and may not know it needs to be fixed.
On the other side, never use Airprint of any kind from a Mac, all it does is limit your ability by taking away all the driver features, it should only really be used from an iOS device.
There is also a newer firmware here
While standard AirPrint works fine  (as long as the printer is connected with Ethernet and not Wi-Fi - in which case it doesn't, but anyway). After securing up the Internet access protocols  & , I have found that adding a printer on the local network now shows a new "Secure AirPort" option as default  and subsequently fails to add the printer resulting with a connection error .
I tried wiggling with some settings, no luck so far, did any one else encounter a simmilar problem, found a solution, or is it just a driver/OS bug - if so, to who should I report it - Xerox or Apple?
Device: Xerox Phaser 3260
Firmware: V3.50.01.11 JUL-15-2015 / Nework: V6.01.14
OS: macOS Sierra 10.12.4 / Driver: 1.02.01