there are many such references, they seem to be increasing, as some have noted we seem to be in the midst/living through a Golden Age of algorithms. some newer algorithm-focused refs [hence not so well known] not listed so far that may be interesting, some written by TCS researchers/scientists/experts, others by popsci writers:

* [Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers](http://www.amazon.com/gp/product/0691158193/) MacCormick
* [Automate This: How Algorithms Came to Rule Our World](http://www.amazon.com/Automate-This-Algorithms-Came-World/dp/1591844924/) Steiner
* [The Advent of the Algorithm: The 300-Year Journey from an Idea to the Computer](http://www.amazon.com/The-Advent-Algorithm-300-Year-Computer/dp/0156013916/) Berlinski
* [Algorithms Unlocked](http://www.amazon.com/gp/product/0262518805/) Cormen
* [Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World](http://www.amazon.com/Probably-Approximately-Correct-Algorithms-Prospering/dp/0465032710/) Valiant
* [Out of their Minds: The Lives and Discoveries of 15 Great Computer Scientist](http://www.amazon.com/Out-their-Minds-Discoveries-Scientists/dp/0387982698/) Sasha/Lazere
* [Engines of Logic: Mathematicians and the Origin of the Computer](http://www.amazon.com/Engines-Logic-Mathematicians-Origin-Computer/dp/0393322297/) Davis

also, other interesting topics from news/headlines with a strong overlap between TCS and popular science writing/books: 

* quantum computing
  * [Quantum computing since Democritus](http://www.amazon.com/Quantum-Computing-since-Democritus-Aaronson/dp/0521199565/) Aaronson
  * [The Feynman Processor : Quantum Entanglement and the Computing Revolution](http://www.amazon.com/Feynman-Processor-Entanglement-Computing-Revolution/dp/0738201731/) Milburn
  * [MINDS, MACHINES, AND THE MULTIVERSE: THE QUEST FOR THE QUANTUM COMPUTER](http://www.amazon.com/MINDS-MACHINES-AND-THE-MULTIVERSE/dp/0684814811/) Brown
* high frequency trading ("HFT"). this is a strong mix between theory and applied and uses advanced machine learning, datamining, statistics, and mathematics techniques. [can name some refs on this but suspect this audience will not regard it as "pure" enough so will hold off for now.]
* cryptography
* etc!