(Disclaimer: I'm not a computer scientist. I wish more people would address this interesting question.)
There are quite a few options out there. A number of texts have titles in the lines of "Introduction to Computer Science", "Fundamentals of Computing", etc.
For example, I enjoyed reading CS for All: An Introduction to Computer Science Using Python last year, although I did not work on its introduction to objects because I had a bit of trouble with the Python graphics library of their choice, so I just glanced the contents since objects were already a familiar topic.
I was satisfied with its treatment of Python, functions and recursion, as well as other subjects I wanted to dive into a bit more, so it was a generally enjoyable read.
I've found it relatively short and now I'm looking for complementary texts. Titles that caught my attention (in no particular order):
- Introduction to Computation and Programming Using Python
- Computer Science Illuminated
- Python Programming: An Introduction to Computer Science
- Explorations in Computer Science
And there are certainly many others available and more or less up-to-date.
BTW, regarding being up-to-date, this is probably bad advice (and possibly worth a separate question), but I once misread the introduction from Simply Scheme (which is also an introductory CS book, and is known as a prequel to Structure and Interpretation of Computer Programs) as stating that CS books have a ten-year-or-so lifespan in terms of how well they address the ever-changing trends from the field (certainly a terrible misread, and people would throw SICP at me as a counterexample - BTW, there is a JavaScript edition of SICP now). But it stuck with me, and now I personally tend to favor more recent introductory CS books such as the ones I mentioned.
So this is just something to consider. You are probably okay reading any book or edition that is not terribly old or adopts an unfavorable language to teach its concepts. Python is a popular language choice now, Java had its heyday, and you certainly can find more or less up-to-date choices for C and other reasonably popular languages you might be familiar with, or even language-agnostic options (such as the Computer Science Illuminated one that I mentioned earlier, with which you are free to adopt any language you prefer).