I think that the separation between titles/territories and noble houses/dynasties is fine. We all need to think in terms of dynasties and noble houses, rather than in terms of cultures, regions and nations, let alone states. From what I know, high ranking noble houses had no links to any kind of region. But of course they had some kind of clientel/personell (thus also local to some extent) base. Just think of the hapsburgs, who originally came from modern day switzerland (Aargau), acquiring Austria and Styria, inheriting Burgundy. Charles I./V. - rather a flaming - then inherited Spain (legend has it that the "flamenco" had it's origin here, a dance for the fleming). His son, being brought up in Spain and bearing the by then still very-un-austrian name of Ferdinando, brought his spanish entourage back to Austria, and it took quite some time until his clientel was "austrianized". For a more medieval example, just google the house plantagenet.
However it seems to be a reasonable point that large dominions should be harder to control and/or establish. For western/central Europe, we're speaking of personal rule without any state-like bureaucratic apparatus. Kings did not have bureaucrats who
extended "their" rule, rather they had to
delegate rule to someone else - high nobles, or, safer, to low nobles/knights (ministeriales). Basically, a king only ruled when and where he was present in person. It is not for nothing that territorial lords did not have residences in the high middle ages, but instead constantly travelled through their dominions (only bishops had some kind of stabilitas loci). Unfortunately, the game lacks any kind of location-bound-interaction. Having a kind of avatar on the map would have fit the characteristics of medieval rule: "Hurray, the emperor is campaigning in Lombardy, now let's all become independent! He won't take note of it before two months!

". Or imagine how kings drown in rivers on their journey to the holy land, or how they are imprisoned by some strange Babenberg Leopold on their way home

. Making vassals harder to control could be an interesting option to simulate the effects of personal rule. On the micro-scale, I'd love to see some
holdings to have the chance to become independent as well.
I also agree that the HRE seems to be a bit too strong sometimes. Instead of high crown authority, emperors could possibly issue some kind of Landfrieden/treuga dei.
Colours/Art
Another point I would have loved to see (apart from a 2d map - 3d maps only have disadvantages compared to beautifuly designed 2d maps like ageods') is an even more colourful presentation of the middle ages. Agreed, paradox has done a nice job, because the game already is colourful to a certain extent. But the stone-masonry menues still evoke problematic pictures of the "dark" middle ages. Now, if we don't look at the countryside, which was always and for most periods "dark" or dull, the middle ages were extremely colourful. The problem is that the 19th and 20th centuries colonized the past with their ideas of romantic-classic beauty. Just as Rome was a multi-coloured hodge-potch rather than a city of white marble, the same is true for the middle ages. Here's a link to a picture that shows what the portal of the Amiens cathedral has looked like (a reconstruction via laser-light):
http://www.dartblog.com/data/2011/01/009373.php
Detail:
http://upload.wikimedia.org/wikipedia/commons/8/8f/Amiens_cathedral_Son_et_lumière_003.JPG
I think that pictures like these can really change the way that we're imagining the middle ages. Vibrant life instead of grey stones!