I would guess that rather than the suggestions made so far, the most like candidate is Edward Gibbon's "The Decline and Fall of the Roman Empire". This late 18th century work of history was ground breaking at its time and very popular and influential, but filled with assumptions, editorialising, and invented narratives. In general it's still the ur-source for a lot of modern cliché's and myths regarding Roman politics.

This is a bit Gibbon wrote on the Byzantine Empire:

The city of Byzantium, later renamed Constantinople and then Istanbul, and the Byzantine Empire were vitiated by a bureaucratic overelaboration bordering on lunacy: quadruple banked agencies, dozens or even scores of superfluous levels and officials with high flown titles unrelated to their actual function, if any.

Access to the Emperor and his council was controlled by powerful and inscrutable eunuchs and by rival sports factions.

Quite likely the later imagining of Byzantium, and the related use of the word Byzantine, have its origin in the picture Gibbon paints here. But I'm not an expert myself, so I can't be sure if this guess is correct.

EDIT: Please see /u/shlin28's reply below. At the very least Gibbon was drawing on already established stereotypes of the Byzantine or 'Greek' Empire, how much further back it goes is yet unclear.

In addition to /u/NFB42 and /u/shlin28 's comments its worth noting that the OED only records the first usage of "Byzantine" as an adjective describing something "intricate, complicated; inflexible, rigid, unyielding" and applied, by itself, to something other than the Byzantines themselves as having been in 1937 and then apparently catching on in the 1960s:

1937 A. Koestler Spanish Test. iv. 75 In the old days people often smiled at the Byzantine structure of the Spanish Army.

1965 Economist 25 Dec. 1404/3 From the byzantine procedural caution of the approach work [to the Common Market] on both sides, it seems that substantive issues are still beyond the diplomats' grasp.

1966 G. Steiner Lang. & Silence (1967) 399 It was precisely on this occasion that Stalin struck the new ominous note of the cult of personality, of the Byzantine homage to the leader.

1966 Listener 26 May 765/1 To hint that one does not quite catch the drift of their byzantine prose..pierces to the heart of their intellectual pride.