Scrap that, it was Heraclius. They weren't a feudal state like France for example, but the organisation of the Empire changed, with no more provinces but theme, who were semi-feudal but indeed very different from Western feudalism. I think the introduction of the themes happened under Heraclius, I think?
Heraclius was indeed the one replacing Latin with Greek in the administration. The themata system is generally atributed to him or Constans II.
I don't know what you see as feudal in the theme system. Themes were administrative provinces not hereditary titles.
If it's the fusing the military responsibilites with administrative one for the strategos then it already began with Justinian's exarchates just put an a smaller and systematic scale with the empire threatened everywhere.
It's not really different to the governor responsibilites of roman provinces before Dioclotean reform.
It's how soldiers were conscripted that really made themata different.