Treadgold, Warren. A history of the Byzantine state and society. Stanford, CA: Stanford UP, 1997.
I like it well-enough and think it's pretty good, but I am almost graduated with my A.B. in Classics, having been steeped in such page-turners as Andrew Wallace-Hadrill's Houses and Society in Pompeii and Herculaneum and Sir Ronald Syme's The Roman Revolution.
I'd say, though, for a general-interest reading, that you'd be better off shelling out for Lord Norwich's three-volume set. He tells the story in a more narrative and episodic way. Treadgold (and, for that matter, Ostrogorsky) doesn't fool around with neat stories. Of course, Treadgold is trying to get about 1200 years into about a thousand pages with an eye toward completeness - relative to both state structure and cultural issues.