Finished UHV on easiest with Hungary and Muscovy.
Hungary:
This time I didn't settle in Austrian lands. Conquered Belgrad/Nándorfehérvár first, and waited for Belograd/Gyulafehérvár to reach size 2 so it doesn't get razed. Unfortunately didn't go for Fiume in time before the Venetians. They became vassals later anyway.
The Austrians could have caused a trouble were I not prepared for them (though it's not a nice thing from me).
I was chosen for the first crusade (even though having a low number of faith points that time), and easily captured three cities (which didn't change names back to Jerusalem, Antiochia, whatever). I think the Hungarian UP probably helped here (no unstability from foreign culture). Interesting to note is that for much time my trade was blocked to the middle east (ie. my cities there didn't get the resources from my european cities). I looked but the ocean trade route seemed like un-blocked.... (Though at some time there were certainly barb ships blocking my shore, one good point for the AI).
The Ottomans spawned with a great number of knights, but somehow managed to disperse or lose many of them. Didn't let them conquer much in Europe, and they collapsed quickly after capturing Istanbul (which also didn't change its name back to Constantinaple or Konstantinápoly) .
One mistake was that I didn't realize I had to build Golden Bull to get the civics early. Germans built it, but luckily didn't use it (it's probably no use for others anyway, as you would get a stab penalty without its complementary civics). So had to wait for some hundred years to research free religion and win. The largest region uhv was automatically won. (Fortunately the Kievans didn't collapse and Muscovites didn't play good, see next section).
Ah, btw, where is the Mongol conquest (Tatárjárás) of 1241? They never seem to reach the Carpathians...
Also, how come Golden Bull gives religion civics? First, it was in 1222 (waaay before even the reformation), and second, it was similar to Magna Charta, it gave rights to the noble classes vs the king (and actually weakened the king's power, or at least acknowledged that it happened).
Moscow:
By the start, Hungary and Kiev had already collapsed. Byzantines collapsed on the third turn. Good thing, no Kiev to fight

Take some time to realize what the first uhv was - I thought first there would be attacks from barbs, but then realized I simply have to conquer back the cities from the barbs.
So for beginners: go for the cities that are barbarian (dark grey/black color) and leave independent cities (grey) alone for now. Capture all black cities early and you're ok with first goal. Then go for the indep cities.
Also, converted to Catholic in the beginning, not historical, but noone else was orthodox by that time. Helped maintain peace and trade. (Though still the AI is outrageously stupid when they think I will trade a tech worth five times what they want to give for it).
As Byzant collapses early in probably most plays, it can be useful to go for some of their cities. I went for Galats (and probably could have gone further) to gain a foothold for conquering Istanbul. The Ottomans start in peace and didn't attack me. In fact, I waited for a long time and eventually they collapsed in the 17th C I think. Though that was probably a waste of time and should've conquered them earlier for a higher score. Still, a large army is needed. These cities are not well defended (with defensive units), but have a large number of bombards and cavalry.
For the 20%land goal, I settled everywhere in Russia, even up north (and build culture), then won when conquered cities in Balkans then two in Turkey.
Not exactly sure if the Kremlin UB was of any use. Nobody attacked me (though there are harder difficulties for sure) and didn't really need the espionage points. Only built them for culture.
Btw for an earlier discussion (about Wien not there) : there are several cities pre-built in Russia...
For both plays: I didn't have a problem with happiness, didn't build a single cathedral, and churches also weren't necessary. (Higher difficulties, again, might need them). Health is a problem, however. This is good, it's realistic. (Happiness should be harder too). Aqueducts and apothecaries come relatively late. (Problems with happiness and health help to promote trade.)
It seems though that the AI has problems with both, their cities are often revolting (even when they are stable) and unhealthy. Maybe the AI doesn't focus on these?
As for stability: didn't have a problem in these two plays, though stab rating only grew to an acceptable level later in the game. For Russians, I used the tactic of not changing civics at all (only after building some wonder that gives 0turns). Now they don't start in the best civics combo... If I switch early, stab can go down to minus (tried it, though luckily cities didn't revolt).
While the stab in the end reached 90, I think the early civic changes shouldn't have so huge effect (even if it is small by the end). I think it would be more realistic and playable, if the religion changes would have a great unstab effect, but civic changes would only have temporary effects. (When protestantism emerged, Austria switched to it, then back in the next turn... how did they do it btw, shouldn't there be a minimum turn wait?)