I just registered as I'd like to add a vote for Humble Store. I have multiple games on it and they come in multiple kind of packages so I guess they don't impose specific package formats on developers. I use Archlinux and I'll write my own PKGBUILD so I'll be happy with a simple tarball, like for instance, FTL, containing directly a folder with the game and its data and necessary libraries. It can be run directly from the folder so it's not really difficult for the less tech savy. Otherwise, the Mojo installer that Double Fine uses for Psychonauts or Brutal Legend is not too bad because it can be unzipped to get its content (without running the installer). At least the one for Psychonauts can be run as a user and the game installs in home, creating shortcuts and all. Maybe it's easier for some people. A deb is not bad either because it can be unpacked easily too. As long as I can unpack (from the command line) and copy the files over, it's fine But first choice would be a simple tarball. And Humble Store can give multiple choices.
On Desura I have only Dungeons of Dredmor so I don't know if all games are distributed the same way, but I just downloaded a tarball from the webpage without using the Desura client. So yes, it would be OK too, if it is not mandatory to use the client and its "features" such as auto-patching and achievements (if I wanted those I'd use Steam).
GOG would be nice too, but as they don't support Linux now, there is no way to know how they would do it. Would they package things with their own installer or more like Humble Store ? From what I have read, part of why they don't support Linux is because they want to be able to provide support for the games (not just post the tarball and let users deal with it).
