Any tips? I've tried most of the civs in this scenario, and it seems like the franks are the only ones that I manage to do well with...
I would say the Celts or the Goths are probably the strongest of the barb civs. Even on Deity, it's pretty easy to win with either. It's not so much about taking all the cities, as it is about rolling Rome and Constantinople as quickly as possible. To this end, it's not really worthwhile to keep most of the cities. When in doubt, raze it. You'll pay for it with a lack of policy upgrades, but the policies are primarily about ways to keep your cities happy. You don't need this if you raze them, and you still get the lion's share of the points for the capture, as well as forcing the Romes into negative policies, so they're at huge penalties by the time you have to deal with any real troops.
I feel this scenario is sort of a brother to the Mongol one, at least strategically.
Celts
The beauty of the Celts is the movement options imparted with their embarking rules, and the pictish warrors. Due to how embarkation works, if you start the turn in water, you end up with 5 movement. So, since the celts can disembark for only 1 move, it means if you start with your army in the pond, you can basically jump out and perfectly surround a city with all your warriors and catapults without wasted turns and soaking up damage to do it. Catapults can disembark, setup, and even fire if they're close to the edge. The second important task is to remember to pillage. Pillaging heals, and your pictish warriors can do it for free. So, if it's a city you're going to raze, then make sure to pillage during the 2nd turn of combat with all your pictish warriors. It's a free heal.
If you head straight down the west coast of Gaul(France), sacking the cities on the way, you should be able to cut across on the road on the edge of the Iberian Peninsula and get to Rome by turn 16-18. From here it depends somewhat on what he has lying around. If he's got a bunch of troops in the area, you really need to come in from the north, so sack Ravena first.
Once you're done, just head east till you run into Constantinople, taking or razing any cities you come across.
Goths
The Goths don't have the same advantages as the Celts, but they have the best start. You are 3 cities away from either capitol, and your troops are OK. The cities between you are actually pretty decent, with good luxuries and resources, so you may not want to raze your way to the capitols like I do with the Celts. Use your workers to chop forest down to speed up your unit production. You should be able to have two separate armies that you can fork off sack Western and Eastern Rome simultaneously. There's a Goth city on the black sea, so you can build triremes to help with Constantinople (which is hard to surround). Depending on the difficulty, you should have both capitols by turn 25 to 30. At that point it's mostly just the Sassinids that might be able to win.
I'm surprised you've had the best luck with the Franks. I feel they have the weakest of the barbarian starts. They're stuck up in the ends of the earth like the Celts, but they don't have the huge movement advantages the Celts do, and their units aren't astoundingly exceptional to make up for it.
Things are just sorta stacked against Rome in this scenario, even for the AI on Deity. I wish it was a little more balanced, actually.
Has anyone ever won as Western Rome on Deity without cheating? I'm not exactly sure how you'd do it. A lot of luck I guess.
