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 use the debugger,
how to use the profiler,
how to solve large problems (a high level language),
how to put together large systems,
how to break down problems (decomposition of problems),
how to avoid writing complicated code,
how to communicate *to humans* the intent behind an (often cryptic) series of executable statements.

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"][1]  and [TelescopeRule][2]

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.

**criteria for a second programming language**

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 [pick the right tool for the job][3],
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")

EDIT:
I find it disappointing that posting a summary of something that I wrote, in collaboration with many others, "may not be a legal post".

So I'm adding a more formal [citation][4] to my previous informal link, attempting to comply with [fair use][5] and other wiki copyright issues.

This answer is a summary of [Freshman's First Language](http://c2.com/cgi/wiki?FreshmansFirstLanguage) (Anon 2011) at the Portland Pattern Repository.

(Anon 2011) Many anonymous and various other authors. "Freshmans First Language". Portland Pattern Repository. September 27, 2011. <http://c2.com/cgi/wiki?FreshmansFirstLanguage>.

  [1]: http://noucamp.org/cp4/cpp/OOPLs.html
  [2]: http://c2.com/cgi/wiki?TelescopeRule
  [3]: http://c2.com/cgi/wiki?PickTheRightToolForTheJob
  [4]: http://c2.com/cgi/wiki?HowToCiteWiki
  [5]: http://c2.com/cgi/wiki?WikiCopyRights