Instead of C, I would suggest something like Python, where you don't have to learn to make your own shoes before you can start experimenting with fashion. With Python, you can forget about the computer and just think about programming. (I'm talking about pedagogy here, not production, where C is often a better choice.)
The fact that OOP was really bolted onto Python as an afterthought means you can learn simple straightline code, then start clustering it into functions as it starts to get more complex then, eventually, start clustering functions and data into simple classes where it (occasionally) helps to manage the growing complexity, followed by your own modules. You don't have to start with packages and class hierarchies just to print "hello, world" as in Java, but you also don't have to reinvent the string, as in C.
you don't have to learn to make your own shoes before you can start experimenting with fashion
I think what you and DanielBMarkham are approaching from opposite sides is that it's useful for a student to learn both how computers work and how computation works.
C is pretty close to the computer. Learning C will teach a student how computers work. That's important for the same reason that a fashion designer should have some understanding of what shoes are made out of and how they're assembled. Making shoes that are nice to look at, but that fall apart when worn is not especially useful.
Python (or Smalltalk, or Scheme, etc...) is closer to how computation works, and closer to how many of the problems people want to solve using computers work. It lets students explore what they can do with computers without getting mired down in the details of how the computer will accomplish the task.
Java is somewhere between, and from an educational perspective, has the disadvantages of both sides without gaining many of the advantages.
The fact that OOP was really bolted onto Python as an afterthought means you can learn simple straightline code, then start clustering it into functions as it starts to get more complex then, eventually, start clustering functions and data into simple classes where it (occasionally) helps to manage the growing complexity, followed by your own modules. You don't have to start with packages and class hierarchies just to print "hello, world" as in Java, but you also don't have to reinvent the string, as in C.