Forum favorite Good and Real looks reasonably accessible to me, and covers a lot of ground. Also seconding Gödel, Escher Bach.

The Mathematical Experience has essays about doing mathematics, written by actual mathematicians. It seems like very good reading for someone who might be considering studying math.

The Road to Reality has Roger Penrose trying to explain all of modern physics and the required mathematics without pulling any punches and starting from grade school math in a single book. Will probably cause a brain meltdown at some point on anyone who doesn't already know the stuff, but just having a popular science style book that nevertheless goes on to explain the general theory of relativity without handwaving is pretty impressive. Doesn't include any of Penrose's less fortunate forays into cognitive science and AI.

Darwin's Dangerous Idea by Daniel Dennett explains how evolution isn't just something that happens in biology, but how it turns up in all sorts of systems.

Armchair Universe and old book about "computer recreations", probably most famous is the introduction of the Core War game. The other topics are similar, setting up an environment with a simple program that has elaborate emergent behavior coming out of it. Assumes the reader might actually program the recreations themselves, and provides appropriate detail.

Surely You're Joking, Mr. Feynman is pretty much entertainment, but still very good. Feynman is still the requisite trickster-god patron saint of math and science.

Code: The Hidden Language of Computer Hardware and Software explains how computers are put together, starting from really concrete first principles (flashing Morse code with flashlights, mechanical relay circuits) and getting up to microprocessors, RAM and executable program code.