With every PC we sell, we include the Tucows (formerly Luxemburg)/Linux Central Application set. It includes over 2600 applications, indexed and categorized, with an easy to use HTML interface.
All of the programs in the set include full source code, and many include binary packages (rpms, debs, tgzs and some slps) for many popular distributions. But you can compile all of the programs yourself no matter what distribution you use.
If you've never used Linux before, you can be sure to find a program in this set to suit your needs, and if you are a seasoned Linux or unix user, you can find some of your stand-by favorites.
