You showed two different statements that do not do the same thing: one allocates a block of memory, the other creates and calls an initialization method on a new object. The second statement does not equate to explicit memory management. Just because creating an object might be implemented by the compiler or runtime as allocating a block of memory from the process heap (which is far from necessarily the case, GCed environments generally just return and increment a pointer) does not make the two statements equivalent. The semantics of malloc is that it returns a pointer to a block of memory. This memory contains garbage and it is entirely up to programmer to do something useful with it. For example, the programmer might use it to store some data of a completely unrelated type, or the programmer might not even do anything with it. It is his responsibility to free this memory when he is done with it. This is not the same thing at all than a statement that returns an opaque reference to an object which lifetime is managed by the runtime. We're not only talking about two different levels of abstraction (one states the intent, the other a mechanism), but the mechanism here is just one possible, incomplete - and inefficient - way of implementing that abstraction.
You said explicit memory allocation was an unnecessary complication in C, or words to that effect by implication. My example was to demonstrate that in reality, there's not much difference in complexity, in terms of syntax and function calls, between malloc-ing a block of memory in C and creating an instance of a class in a higher level language. What the relevant functions / language constructs do is immaterial.
As for namespaces and header files - not the same thing whatsoever, the first is a type qualifier, the second is a form of hand-written metadata to enable to compiler to treat each source file in isolation so it's purely a compilation mechanism; include directives create an implicit graph of inclusions and beginners inevitably run into multiple include and circular dependency issues, with their appropriate solutions - none of which are useful or generally applicable CS concepts, but accidental complexity of a specific language.
You offered that other langauges also provide data types that map to hardware abstractions, but I nuanced that other languages also provide data types that do not map directly to hardware abstractions. It is a particular design choice of C to only offer data types that map to hardware abstractions. Thus C offers a level of abstraction that closely follows how hardware works. But this level of abstraction is not a particularly useful one for the purpose of introducing the topic of programming and computer science in general. Execution speed is largely irrelevant for teaching purposes. Just looking at the different areas of computer science, about the only one I could say that C is a particularly good fit would be Computer architecture and engineering. C has far too few concepts to be interesting to programming language theory, it's missing several common and useful abstractions for data structures and algorithms, doesn't contain any facilities to help with numerical analysis or computing theory, nevermind concurrency and parallelism, databases, software testing, etc.
All of which at some point has to be reduced to machine code. I'm not sure what your point is here. The integral data types for most languages behave the same way. If C has less abstraction and executes quicker, that's a positive attribute.
But that's irrelevant. Just because higher-level languages include constructs that are similar to ones offered by C does not make C a particularly good fit as a first programming language.
Any higher level language worth its salt should translate those same simple constructs (if/else, loop/while, switch), which are present in most languages, into similar machine code eventually.
Yet they still have similar simpler constructs, just like C. All of which can probably be reduced to the same cmp/jmp instructions.
Well there's the crux of the issue. You're talking from the point of view of teaching computer architecture, and in this respect I agree that C would be a good fit, notably because C's level of abstraction is close to that of the hardware. I'm talking from the point of view of an introduction to programming and computer science in general, which includes countless topics aside from computer architecture; therefore I favor a language that will be as simple to learn as possible and teach generally applicable and useful abstractions to students that they can then apply to various fields and languages.
Abstractions hide what's happening and complicate the thought process. That's why I'd never suggest someone start with an OOP language. I don't think that's suitable for a beginner who wants to learn how software and computers work.
One classical introduction to computer science, and I've referred to it often in this thread, is the Structure and Interpretation of Computer Programs used at Berkeley and MIT. If you look at this book, you will see that it touches on many topics that one could not dream of approaching in an introductory course if the teaching language was C. It is able to provide a vast outlook in part because it uses the right level of abstraction to do so. Courses based on this method are notoriously hard but provide an extemely solid basis for the rest of the curriculum.
As for recursion: perhaps you missed that even the "iterative" version of quicksort is recursive as the quicksort procedure calls itself; only the partitioning is done iteratively. And you didn't address my point on tree structures which are at the basis of many typical data structures and algorithms. You seem to simply dismiss anything that C doesn't support as unimportant, back-handedly referring to functional languages as "whole different category" (what does that even mean?) and equating higher-level features with potential C implementations as if C was somehow the reference point of all programming languages. I understand that this is what you use in your daily work, but it's just another language, and there's little about it to make it attractive as a first programming language, apart from the low number of concepts; but if that's to be the only criteria, then assembly is even better because there are even less concepts in assembly - and you can make much of the same arguments you make about everything eventually compiling down to machine code and hiding what the computer is doing to justify using assembly. At that rate, even C is far from ideal.
Thanks for pointing out that there's an up-to-date C++ REPL, perhaps if it was adopted in more learning material it might make C more approachable for beginners.