Played Byzantium, Sweden, France and Kievan Rus' so far (Beta). All on middle difficulty.
Overall impression: very nice quality for beta stage, though some of UHVs were really easy.
1) Byzantium - Domination win 1588 AD
Originally tried to get historical, getting 1st one was pretty easy, killed arabs as soon as they spawned, and always suppressed their resurrections with cataphracts and later on knights.
First real challenge came at 11th century with Seljuks. Was completely caught unprepared 1st time, had to reload and build walls/guisarmiers/knights. After I fought them off, France asked to become my vassal, I accepted and got in the war with Germany. Sent like 7-8 knights, captured 2 cities from Germans, they capitulated.
In late 13th century failed 2nd objective (1 of cities revolted) and Turks spawned. It would be pretty hard to fight them off if thay wouldn't leave their only town with 2 or so defenders, which allowed me to just capture it with knights and thus eliminate their army. Later I suppressed 2 of their uprisings, 1 time they revolted simultaneously with arabs.
Went on to war with Hungary and Austria, Hungary collapsed, their cities went to me after, Austria vassalized to me, but collapsed 3 turns later, so I took their cities as well. Colonized Poland as well which also collapsed soon after. Then I sent my knights to capture mongol cities in what before was Kievan Rus' as I saw my tech situation worsening quickly (stability was always around -50 collapsing) and decided that only opportunity to win lay in quick rush to domination. 1566 AD save attached, close to victory.
2) Sweden - historical 1750 AD win
Easiest of all 4 I think so far. Killed Norse as soon as game started, settled Finland with 3 cities. Only setback was to have plague just at start. Karolins really do seem like cheat in a world that doesn't have flintlock yet with their 40 hammer cost to produce. Beelined cuirassiers-cannons-dragoons later captured German cities (Germany has collapsed before I started game), vassalized Poland.
There was nothing to do but wait for 1750 AD so I decided to make it more interesting, and when in 1686 Ad Muscovy declared war on me, I went with half of army to own them, this advance was stopped only near Moscow itself, and simultaneously declared war on France, which eventually lead to capture and raze of Paris. Morale : you can win a war on 2 fronts if you're playing RFC:E Sweden

Save of 1730 AD attached.
Ah, forgot, made my Sweden orthodox
3) France - time 1800 AD win, 6x Industrial Revolutions
Just started a peaceful builder game, went on building wonders, vassalized Burgundy occasionally (misclick) so basically that put an end to UHV hopes. Still completed 2/3, had holyland region also after leading 2 crusades there. Had a war with Spain out of boredom in 18 century (cities basicly had all buildings, I built pretty nice army and had to use it

) Ottomans almost caught me on score in the end, but collapsed at like 1780s, my France finished with just over 4k points.
4) Kievan Rus' - Historical Win beginning of 15th century.
Was fastest of all (2hrs of play). Just built a lot of Druzhinas, held off mongols and spread along Black Sea coast. Vassalized Bulgaria (peacefully), captured Constantinople in 1300s (surprisingly it was guarded by 1 Arbalestier, who couldn't defend vs 5 Druzhinas even with this "so insane" Theodosian Walls bonus).
Now, being a Russian and knowing our history a bit, some remarks on Kievans (didn't play Muscovites yet). Starting year could be moved 880 AD -> 862 AD (it's widely considered as official start of Russian History (Primary Chronicle says it was the year when Varangian princes were asked to rule over Rus')). Second, it was lol whe I had a capital named Khabarovsk (actually, it was some wierd bug in that game - first, cities' names didn't change depending on location; second, cities didn't rename on capture, for Example, France had Mediolanum, Turks had Hadrianopolis, not Edirne etc.). Only thing I changed manually in python is that getcivilizationshortdescription->getcivilizationdescription in CvMainInterface.py twice.
Anyway, save is attached (just before victory).
At last, Veche Hall makes little sense as there were basically 1 city that was a veche republic for a long time, and it was Novgorod which at that time already was independent (Novgorod Republic), not under Kievan control. Though can't really think of anything better at the moment
