I've listened to all 112 episodes so far (and still quite a bit to go) - once this finishes I'll probably go back and listen to the "12 Byzantine Rules" again - which is also very good.
Although not purely a podcast, I can also strongly recommend the BBC Radio 4 series "In Our Time" - which is available as a podcast:
http://www.bbc.co.uk/radio4/features/in-our-time/
This is an informal "history of ideas" and is the kind of thing the BBC does extremely well.