I'll second Nagel & Newman. I read that in college and met a few times with a math prof to talk about it. What fun to work through the whole proof and see each

I'll second Nagel & Newman. I read that in college and met a few times with a math prof to talk about it. What fun to work through the whole proof and see each piece build on the last! Now, over 15 years later, I'm still telling myself to read GEB, but I always wonder how much point there is. A very worthwhile book to read in parallel to N&N is Euclidean and Non-Euclidean Geometries, by Greenberg. It's more textbooky, but still short, and it will let you see how some of the same themes played out in geometry as well as arithmetic.