Can we *also* distribute a .deb package? Will itch.io download just the first linux download, or pick one at random?
Of course! Feel free to keep .deb and .rpm files on your itch.io page, itch will only pop up the policy dialog if they're the only option for Linux.
You can ship both, but mark the Deb as for no platform and mark the portable archive as Linux, so that Itch knows what to download. You can still put "Linux" in the name of the Deb package.