I'm playing the Roxoloni on Hard/Hard, and I have some impressions from my campaign that may help some people. First off, your biggest enemy is economic, not military. The Roxoloni have capable infantry (although it takes a while to get), great archers, and excellent cavalry/cavalry archers, and with some skill you can defeat most armies larger than your own that will be tossed up against you. The unit lineup is identical to Sarmatia, but they require 15 to your 10 settlements, so this is a good warm up if you want to challenge yourself with Sarmatia later on.

In my game, I built up an army of archers, horses, and spearmen, horded, and then headed for the city of Salona, sacking every ERE settlement along the way for that extra cash I knew I would need down the line. After that, I took Salona from the WRER, and dispatched my remaining horde forces to the city to the upper right, held by the Huns at this point. After kicking them out, I had a dinky little empire with enough forces to hold both from the retaliation by the WRE. The Huns were settled (and therefore weakened enough) to agree to a ceasefire (although I had to grease their palms) and trade rights.

The economy started to hurt me pretty quickly, though, since I was at war with the WRE, WRER, and the ERE. None would agree to a ceasefire, so I took the fight to the WRE and eventually took all of Italy and the island of Sicily. This gets the money pumping, and hurts the WRE enough that they might agree to a ceasefire.

The sea trade is your biggest asset, and maintaining friendly relations with the coastal factions nearby can help. But if they won't trade with you, simply acquire their ports for yourself, you need 10 provinces, anyway. Once you have enough income to keep a positive cash flow (exterminating cities you capture is virtually the only way to keep them happy, and gives you some temporary surplus to replace buildings if possible to reduce cultural penalties as well as hire troops), venture inland, but only so far as is required by your faction goals. Take Aquincum, garrison it, and then keep with the original plan of going after port cities.

Greece is an excellent target, as well as the city in Macedon, as they have ports and bring you closer to Colchis. That's going to be the most troublesome city to deal with, and I preferred to leave it to last to conquer. Going to war with the Sassanids, while inevitable, can be avoided til relatively late in the game. You need their trade for as long as possible! Ideally, you want to have at least 9 settlements other than Colchis between Italy and Greece. If the Sassanids have Asia Minor by this point (a likely scenario), why bother going to war when you can launch a raid on one city and attain victory? Holding Asia Minor is annoying at best.

One of the best things I did was sack the ERE cities, it left them rebel in my game long enough that after I took Italy and Sicily, I was able to take them from relatively weak rebels. And as a side effect of spending all of that time (I starved them all out), the other horde factions spent themselves or settled before I did, allowing me to get last choice of settling area.

And for Tyrac: I would reccomend your 3rd possibility, Constantinople is a good spot, but you are further away from Rome where you can expand the easiest. You need easy conquests in the beginning due to a lack of funds to make bigger armies. Plus the Roman cities allow you to train all of your best units as soon as you take them.