For the empire's long history, I think one of Judith Herrin's Byzantium: The Surprising Life of a Medieval Empire (2008), Averil Cameron's The Byzantines (2009), or Jonathan Harris' The Lost World of Byzantium (2015) is your best bet. Byzantine Studies has made some enormous progress recently and older books simply do not reflect our more nuanced understanding of the empire's history. These three books were all written very well for a general audience and the three historians mentioned here are genuinely some of the biggest names in Byzantine studies, so they are, in my opinion, the best and most accessible overviews of eastern Roman/Byzantine history. Peter Sarris' Empires of Faith: The Fall of Rome to the Rise of Islam, 500-700 (2011), Mark Whittow's The Making of Byzantium, 600-1025 (1996), and Michael Angold's The Byzantine Empire, 1025-1204: a Political History (1997) are meatier books by specialists and more geared towards students making their first forays into Byzantium, but they are still narrative histories and so should still be relatively accessible if you want more details on specific periods.

I'm currently reading Judith Herrins "The Formation of Christendom". While the focus is on the formation of the Christian church it deals in general terms with most of the late antique world. She's just a very well researched and articulate historian. If you wanted something a bit more general you could dig into either "Byzantium: the early centuries" by J.J. Norwich or the "short history of Byzantium" by the same author.

The Alexiad by Anna Komnene, massively biased 12th century Byzantine princess account of the life of her father, emperor Alexios I Komnenos.

The Secret History by Procopius, vicious and hateful 6th century account of the rule of emperor Justinian and empress Theodora, and also of general Belisarius.