How about a program which can beat me at chess? It runs in 640K on DOS (as well as on unix). With the "difficulty" set high enough to school me, it can generate a typical move in about 30 seconds (on a 220MHz celeron). With the difficulty set high enough to beat my father (a class-C-ranked chess player) it took about 2 minutes per move. And all without an opening book!

(Sorry folks, written in C++ (the kind that relies heavily on C).)