So, Nitro, you asked for feedback. Here it is.
I played up until a few turns after Germany's spawn before dinner time and this is what I noticed.
First of all, as I feared (and kind of hoped

), Nova Roma is much too powerful. Honestly at first glance you can't tell that it's not the full Roman empire! (Justinian did his work well!)
Anyway these were the results. Rome gave me open borders right away so I sent my galleys into the Med. basin and saw everything.
Arabia took the initial flips but either went to war with Rome briefly and unsuccessfully or not at all. I'm guessing the former since As-Sur/Tyre/whatever was burned before I got there to see what that worthless city is called. Power graphs showed Rome as being about twice as powerful as Arabia at spawn. I will note that I sold Rome Feudalism as soon as I met them (about the time Arabia spawned) but this is before that could have an effect.
Thereafter Arabia has turtled and has four or five cities. It has not expanded into Africa despite weak defenses there.
They also converted to Christianity after the first Eurokids spawned. Persia was also Christian.
At this point Spain and Germany have slightly dented the empire but that shores up Rome's economy more than actually hurts them.
The one major blow they had is that by the time I penetrated that far, Constantinople had been seized by fierce barb stacks. This, however, made their capital... Rome.
They aren't falling anytime soon.
These are my suggestions for making them weaker:
First of all, all the western parts of the empire had just been reconquered after a lapse of a lifetime or more. They weren't deep in the Roman fold and were constantly threatened by the various barbarians. As such I could see a case for either: weakening the culture, defensive bonus, or even leaving the cities in active resistance. At the least I'd put swarms of barbs in Spain and north Italy (Are you sure they held Mediolanum in 550?). Historically these cities should fall out of Roman hands within a handful of turns.
Also, I think it was a fluke this time, but barbarian pressure on Italia should be stronger than on Constantinople itself... that didn't fall to barbarians until 1204 (the French

) and still reclaimed it after that.
But I think the most important thing is to somehow make SURE Arabia declares on Rome, and Persia also. They should probably also have a better military but I didn't see exactly what they had. Or how they did against Persia since that's inland.
On the plus side, Germany and Spain at least are both at war with Rome, and keeping it in check at least. Of course without Arabian pressure on North Africa that doesn't really matter.
Those are my observations so far. That and my perpetual one that I really don't know how to do well as the Vikings! Bah.