I few weeks ago, I wrote a review of the book Justinian's Flea: Plague, Empire, and the Birth of Europe. Darryl Rosin left a comment asking if I'd listened to the 12 Byzantine Rulers podcast by Lars Brownworth. I hadn't then, but I went out that day and downloaded it to my iPhone. I've been listening to it over the last few weeks and really enjoyed it. Lars has a great presentation style and makes the material accessible and interesting. If western history in the first eight centuries AD has always been a black hole for you, this will get you up to speed.