If we want to build for Linux we need to get a Linux computer and haven't really decided on doing that yet!
Linux is rather easy to set up. I personally would recommend a standard Ubuntu environment, as that is what GM recommends. If I were you, I'd set up a Virtual Machine in QEMU or VirtualBox.
I think a .deb would be fine enough for the majority of Linux users to use. If you guys can't (or don't have the manpower to) test a Linux release, I'd love to help out. I'm just trying to get your games to an audience who can't appreciate them at the moment.