I've been searching for excellent Church History books and a common denominator to most of the lists I've found had Henry Chadwick's "The Early Church: The story of emergent Christianity from the apostolic age to the dividing of the ways between the Greek East and the Latin West" on it. This is volume one in The Penguin History of the Church series, and you may read most of it online at Google Books. 

Henry Chadwick was a historian and an Anglican, and was a professor at both Oxford and Cambridge. His The Early Church covers the first six centuries of the Christian Church's history, beginning with nascent Jewish Christianity and ending with established Christendom at the time of Gregory the Great. The book is a short entertaining and accessible read that retells history primarily by discussing the most famous theologians of each epoch rather than a complete history of all the world (otherwise it would be a very long book.) 

"Ecclesiastical History" by Eusebius of Caesarea is an infamous classic that covers the same period of time as this book, in much more detail, yet Eusbius, like other early historians spill most of their ink in apologetic responses to early heretics. Chadwick's book is much simplier and easier to read, and may be a relief to those who have struggled with Eusebius, but it is no replacement for Eusebius's great work. So I recommend this as a good introduction or summary of the early church however, its important to remember that so much had to be ommited to cover three centuries in three hundred pages.

Another survey book that is similar to Chadwick's Early Church is a short history that I read recently by Hans Küng called, "The Catholic Church: A Short History." It's also a brief introduction that covers all of Church history up through today in a brief survey format from a Roman Catholic perspective. 

In Chadwick's book he praised a few theologians above others, in particular Origen, Athanasius and Augustine. Also Tertullian and the Cappadocian fathers monopolize many pages. One interesting feature was the discussion about Christian Cryptograms, one of which is an anagram for "Out Father, Alpha Omega: (AO Paternoster)" that may be rearraged from the following square:

NOTAS
OPERA
TENET
AREPO
SATON

I recommend this book as a fun and non-technical introduction to early church history.