I recommend Journey Through Genius. It runs through many different topics, and is focused on proving theorems that were major (but whose proofs are still elementary). For example, it starts with the infinitude of primes, the quadrature of the lune, eventually discussing uncountable sets. I like it because not only does it cover many time periods, but it also conveys well the idea of proof in mathematics - which is a part of math which often is foreign to non-math majors.
The chapters make it quite suitable to skip around as well.
