General Church History
A History of Christianity by Kenneth Scott LaTourette (dated but still excellent)
The Story of Christianity by Justo L. Gonzalez (Up to date, but he really screws up Chalcedon)
The Path of Christianity: The First Thousand Years by John Anthony McGuckin (McGuckin is a Romanian Orthodox Priest, but he has done his homework)
Century Studies
The Emergence of the Catholic Tradition, (100-600) by Jaroslav Pelikan (A standard work, volume I of a series)
The Fall of Jerusalem and the Christian Church, Second Edition by S.G.F Brandon (A study of the impact of the Roman destruction of Jerusalem, and its impact on Christianity. Caution: Brandon is not committed to inerrancy.)
How the Second Century Shaped the Future of the Church by Michael Kruger
The First Seven Ecumenical Councils (325-787) by Leo Donald Davis, S.J. (Good study by a Roman Catholic priest)
From Nicaea to Chalcedon by Frances Young
Personal Favorites
Destroyer of the Gods by Larry Hurtado (Addresses how Christianity challenged ancient cultures)
Warriors of God: The Great Religious Orders and Their Founders by Walter Nigg (a spiritual study of monasticism)
Descent of the Dove by Charles Williams (Williams was a novelist, an Inkling with C.S.Lewis)