Spivak
Jaynes
All good books, all pitched at a level that is very ill suited for what is being asked for.
To the GP, "math for English majors" is a common enough course schema that I think looking at a few syllabi might score you something.
Otherwise I basically agree with your comment. I just take issue with calling Concrete Mathematics a graduate textbook, because I hear people say that as though it’s not an appropriate recommendation for learning. That gives me the impression they’ve not actually opened up a graduate textbook in math or computer science. Concrete Mathematics might not be year one material, but you can do it after a calculus course and maybe an algorithms course. Contrast this with an actual graduate course, like convex analysis and optimization. Textbooks at that level would definitely not be accessible for most undergrads.
I would certainly recommend giving it a shot for anyone interested, as it’s a lovely book full of fun problems. As you say, it’s accessible to well prepared undergraduates.