For the Empire, consider that by their personal names, place names and heraldry they are more byzantine/eastern roman than classical roman. Hence Greek first names and titles would suit them better. Kaisar, Sebastokrator, Basileios, Archon (already in the game), Strategos, Droungarios, Eparches, Despotes, etc. would be better than original latin titles or the forcibly latinised ones of later periods (like baro, marchio, vicecomes and nobilis homo).
PS: Please don't use google translate or the likes to obtain "latin" titles. Stuff like Magnus Dux makes me cringe - there is no such concept as a Grand Duke in classical latin, "dux" being solely used to neutrally refer to leaders/tribal chieftains (cf. the dux aeduorum in De bello gallico).
Dux and Comes might be employed like titles for late antiquity contexts, but again mostly for the western part, not for our pseudo-byzantine Empire of Calradia.