This answer is a summary of Freshman's First Language on the corporate wiki of Cunningham & Cunningham, Inc.
Fascinating question; I like your emphasis on objective criteria. We want freshmen to learn:
programming concepts: The first programming language must support: function calls, iteration, recursion
fundamental ideas: The first programming language must support arrays (for the first steps in a gentle introduction to how how memory really works and how pointers work)
practical programming skills: how to UseTheDebugger, how to use the profiler, how to solve large problems (a HighLevelLanguage), how to put together large systems, how to break down problems, how to avoid writing complicated code, how to communicate to humans the intent behind an (often cryptic) series of executable statements.
decomposition of problems.
the fact that pre-written libraries exist for things like sort(), and how to use them -- i.e., the fact that it's not necessary to write everything from scratch.
Other criteria for a first language:
interpreted (quick feedback helps the learning process).
an interactive environment which speeds learning, testing, and debugging.
high-quality source code is available for students to read in that language
"easy to read", "syntax that approaches natural language" (to make it easier to read and grade the SourceCode)
portable (runs on Mac OS, Windows, Unix). At least one free software implementation of the language.
fast to teach, "few gotchas" -- for example, "[I]t may be faster to first teach beginners Python and then Java, rather than Java as a first OOPL." -- "Comparison of Object-Oriented Progamming Languages" and TelescopeRule
Matthias Felleisen developed a programming language with error messages tailored to a beginner audience. He emphasizes that the particular language choice is not as important as teaching a good design methodology. In fact, he sees the first CS course as a Liberal Arts class, teaching critical thinking, problem solving, and attention to detail.
Stuff we want students to learn, but perhaps this can wait for the second programming language:
a "relevant" language that is "not too esoteric"; something "popular in the industry"
Complexity theory: how to recognize tasks that are impossible with current technology.
higher-level stuff: how to PickTheRightToolForTheJob, how to use a compiler, structures, object-oriented programming, functional programming, logic programming, compiler design, composing and manipulating functions (in the Lisp/ML sense), concurrent and distributed programming,
low-level stuff: pointer arithmetic, computer architecture. memory management, stack frames, assembly programming, machine architecture, device drivers and operating system design (so the machine won't "seem like some frightening black box they can't penetrate")
