Intro to Linear Algebra: http://math.mit.edu/~gs/linearalgebra/
Strang does a GREAT job explaining the intuition behind linear algebra. The book is targeted at first-year undergrads and an adult with just high-school math could work through it.
Bonus: if you're interested in machine learning, you must learn linear algebra.
More advanced is this Strang masterpiece: Intro to Applied Mathematics. http://bookstore.siam.org/wc02/ It covers a lot of the applied math that we focused on pre-AI and pre-cloud computing. Diff eqs, diffusion equations, Fourier analysis, numerical methods, phase plane analysis, optimization, complex anlaysis.
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.
Here’s some off the top of my head. I really think these will help you build a good foundation for mathematical thinking.
Concrete Mathematics by Graham, Knuth, Patashnik
Spivak’s Calculus
How to Prove It by Velleman
Polya’s How to Solve It
E.T. Jaynes’ Probability Theory
Conceptual Mathematics by Lawvere and Schanuel