In that vein, I highly recommend his lectures titled "Quantum Computing Since Democritus". His notes are amazingly written: http://www.scottaaronson.com/democritus/ and largely cover complexity theory from the ground up (not just quantum computing as the title suggests). His lecture on the Anthropic Principle also makes interesting reading.