The Byzantine Empire is one thousand years long, and is composed of widely different periods; I don't exactly know “which” Byzantine Empire you are after. To get a feeling of what each period looks like, the Cambridge Histories probably are a good idea: there is a recent (2009) Cambridge History of the Byzantine Empire; you can also look up chapters on the East in the various Cambridge Medieval Histories. To help you helping me, here is a rough periodisation:

1. 400 - 650: actually, many modern scholars tend to reserve the appelation “Byzantium” for the period that starts just after, and to speak of the Late Eastern Roman Empire before the 7th century. This is a dramatic and fascinating period (Persian Roman wars, incredibly active economic and cultural life, the rise of Islam…), but it is probably quite unlike what you may imagine as Byzantine history. However, if you feel an attraction for Late Antiquity, this is a great place to start. Peter Sarris' Empires of Faith (2011), though it encompasses Western history as well, offers a very interesting account of the political history of this period.

2. 650 - 1025: from this time period on, most historians will feel confortable using the term Byzantium. At this moment, the Empire lost its universal aspect, to become an Ægean power, centred on Greece, the Balkans and Anatolia. In many ways, this period is also the embodiment of many Byzantine clichés — porphyrogennetoi emperors, compendia of ceremonial rituals, ruthless mutilations, strange titles and icons. The beginning of the period is quite poor in terms of sources; the 10th century, on the other hand, is very rich. I really liked Mark Whittow's The Making of Orthodox Byzantium (1996), which provides very interesting remarks on several important elements and an acute perception of historical problems, but should be complemented with simpler narrative accounts.

3. 1025 - 1204: in many ways the continuation of the previous period, it is also quite dramatic — the rise of Venise challenged Byzantine maritime supremacy, the Empire boundaries changed a lot, the dominance of the West became more and more obvious… it also involves very interesting sources, like Anna's Alexiad or Psellos' Chronographia, which are probably some of the most entertaining works you can find in medieval historiography. Apparently, the best-known handbook is Michael Angold's The Byzantine Empire, 1025-1204, but I don't know what it is worth.

4. 1204 - 1453: diplomacy, wicked Venitians, evil Turks, desperate struggle for survival, and the swan song of Byzantine culture. It is certainly less distinctive than other periods of Byzantine history, mostly because its prospects of territorial recovery had become all but inexistent. However, it is endowed with an authoritative and very entertaining narrative, The Last Centuries of Byzantium (Donald Nicol — its only flaw is to be a bit older than the others: the first edition was written in 1972. I don't know if the reedition twenty years later included a revision).

In addition, Cyril Mango's Byzantium. The Empire of New Rome covers cultural history of the entire period.

If you're looking for a primary source that will give you a solid foundation (to build upon) in Byzantine history, I highly recommend (as /u/GeorgiusFlorentius mentioned) Anna Komnene's Alexiad.

It chronicles the Byzantine Empire during one of the most pivotal eras in its history, that is, the reign of Alexios I Komnenos, starting a decade after the disaster at Manzikert in AD 1071 and leading up until the death of the Emperor in AD 1118. But not only does it elaborate on the Byzantine world and much about its history, but it also puts the Empire in perspective, because it also involves many external factions: the Sicilio-Normans of Robert Guiscard, the Crusaders of the First Crusade, the Pope, the Holy Roman Emperor, the Turks, and many others. Best of all, it is written by a woman, which makes it doubly valuable to historians because it sheds light into their status and role (which may be surprising to some).

For me, it is the single most valuable Byzantine source that we have ever uncovered because of these features, and from reading it, I am virtually certain you will not only learn a lot about Byzantium from Anna's narrative, but will also gain an appreciation for her and her Empire too.

As a brief background that will help with an understanding of the narrative of this grand thousand-year Empire, pick up Norwich's A Short History of Byzantium. While some consider it more "pop history", I find that it is a quick and fun read that tells the basic story of the Romaioi, which will allow you to begin understanding what Byzantium was all about. From there, you can move on to more comprehensive academic works.