It means reducing lines of code, by removing redundancies or using more concise constructs.
See for example this famous anecdote from the original Apple Lisa developer team:
When the Lisa team was pushing to finalize their software in 1982, project managers started requiring programmers to submit weekly forms reporting on the number of lines of code they had written. Bill Atkinson thought that was silly. For the week in which he had rewritten QuickDraw’s region calculation routines to be six times faster and 2000 lines shorter, he put "-2000" on the form. After a few more weeks the managers stopped asking him to fill out the form, and he gladly complied.
Yes, it's simply a recurring phrase in the title of several papers, starting from a couple in the 70s, in which Sussman and Steele demonstrate the use of lambda calculus for programming, by means of a minimalist Lisp dialect named "Scheme" they devised for the purpose. You can find the papers themselves here; they're interesting and surprisingly relevant.
I'm not sure if this is ever explicitly stated, but it's clear (from context, having read the papers, and knowing the general background and research interests of the authors) that the phrase is simply a catchy slogan for their contention that lambda abstractions, as a computational primitive, are not only universal in the formal sense (of being able to encode any program in some fashion, however awkward), but universal in a practical sense that any and every construct present in other languages, even those that are baked-in from the ground up, can be reimplemented in a lambda-based language in a way that is both effective and natural to use.
The repeated phrase leads to the obvious generalized form "for all X, lambda is the ultimate X", which is the sense I've generally taken "Lambda the Ultimate" to mean as the blog name, noting that LtU is concerned with programming language design and theory. Ironically, LtU would probably also be one of the best places to find someone who could tell you about something for which lambda is not the ultimate implementation. :]
Note also that Sussman is one of the authors of SICP, a very influential textbook that also uses the Scheme language and spends a fair amount of time introducing lambda abstractions as a concept.
Best Answer
Legacy code is based on the phrase of a legacy system that specifically applies to code. According to Wikipedia it probably dates back to the 1970s and was in common usage in the 1980s. It took off with the tech explosion of the 1990s.
This can be seen with Google's ngram viewer: legacy system,legacy code
Digging into this further, you can find documented uses of the term 'legacy system' in the 1970s.
The earliest example of 'legacy system' that google has is in a book on Proceedings of the Army Numerical Analysis and Computers Conference from 1978:
There is also an example of 'legacy system' being used outside of the technology industry in Clout: Womanpower and Politics grin 1976:
Beyond these example which shows its use has extended beyond the pure software world, the specifics of where exactly the term originated are probably lost to the sands of time. Given the military and political references, it may have originated with them (primarily the military and its jargon migration ("It seems likely that 'kluge' came to MIT via alumni of the many military electronics projects run in Cambridge during the war (many in MIT's venerable Building 20, which housed TMRC..."))