I have actually seen multiple lets play (Quill18, Arumba and DDRJake) from The Cossacks, and I think i would go as far as saying that it became (A LOT) easier from smaller nations... Securing alliances became easier as long as you make sure to not be desiring same provinces, you can force set yourself to treathened to specific nations, granting a 20 bonus for alliance with rival nations and it's a lot easier to call people into war on your side (just promise them some land).
Sure, they want something in reward, but from what I saw from DDRJake, as long as they don't desire all the provinces from the person you are attacking, they will not get mad if you only give them like 1 province and take a shitload for yourself...
And there is no longer the 10 year wait time to call in again, so you can just do back to back wars and each time you just give them like 1 or 2 provinces while taking a lot more...
Wait for the expansion to actualy be available before already screaming stuff... It's just useless if you have not yet experienced the game..
Also, at last: Byzantium IS NOT SUPOSED to survive/be strong. It was a decadent nation at this point, at the verge of being whiped out...
Second: Most small nations DIDN'T grow huge, in general in this timeframe, for the western nations, the rule was: The big nations got bigger and the smaller stayed the same/got conquered. (of course there are some exceptions, but those are exceptions...)