Just a couple of half baked thoughts, inspired by the discovery of io and recent social network hacking. First, implementing a library for graph representation and large scale, complex network experimentation, think networkx for Python, would make a good benchmark application for learning a new language. Such a library engages concepts that should be easy to understand, is easy to map on common datatypes, enables a bunch of fun algorithms and can exercise interactive facilities like GUI toolkits. Add in the large scale aspect, e.g. implementing a set of important social network analysis algorithms/processes on 100,000 node graphs, and you'd get a decent non-numeric performance benchmark.
Congruent to that, I wonder how interesting a whole intro curriculum that exclusively used complex networks for motivating examples could be? Again, I think the science of complex networks could be made quite accesible, yet programming simulations of such networks or derivative applications could easily cover all of a CS1 curriculum.
It'd be a hoot for the students to keep progressing in a CS degree and saying, "Hey, didn't we talk about that in Intro. Programming!" And who doesn't want to know why Kevin Bacon is (not) the center of the acting universe.