What would you choose and why?
The C subset of C++, with a few quality of life exceptions - no need to torture the students with printf codes when there's std::cout. It will teach the fundamentals of how computers work, without any hidden magic.
Pseudocode is a good starting point for a programming task, especially when teaching, to convey the high-level solution without the added confusion of unfamiliar programming syntax, but it alone is, in my lay opinion, insufficient. Without seeing any results it might be hard to keep students interested, and it won't uncover any mistakes in thinking, won't teach the rigorous attention to detail needed to create a working program. E.g. using <= instead of <, or off by 1 errors, or any number of other bugs. Like it or not, learning to deal with such 'trivial' details is a big part of programming.
I say the C subset only because virtual functions, templates, inheritance, polymorphism, and destructors are a bit much for beginners still coming to grips with the basics. But in principle, once they understand how it works behind the scenes, I don't see the harm in using standard containers and other niceties.
If not limited to the options mentioned I would go with Javascript.
It's easy to learn and covers the basics, while also having a common syntax similar to many other languages. No setup or installing needed, you just need a browser that everyone already has, it's very accessible. It's also probably the easiest way to get some UI and make something that can be used, being able to introduce buttons and inputs is great for getting people excited.
Otherwise I would go with Python. Maybe a bit more setup, but similar to JS in how quick you can get to results.