Can't say much about linux on a falcon but I was told that X with linux is much slower than X with MiNT+GEM. Also if I remember correct the linux X runs only in monochrome, but I'm not shure here.
A big number of gnu and other unix programs can be compiled for MiNT, some with few work and other with heavy work. This depends on the quality of the sources. I also found some packages which could be compiled without some work out of the box.
The libc used for MiNT is called mintlib and mostly complete. Posix threads can be used with the gnu pth library.
Virtual memory isn't supported (yet) but mem protection can be used with 68020 and above.
For more information about MiNT see
http://wh58-508.st.uni-magdeburg.de/sparemint/ and
http://www.freemint.de/en/
