Start date: 867
Anywhere in Ireland or England sounds like where you'll want to be. Even 1066 in Ireland is still good.
If Ireland and England is not your fancy, basically the 867 start date is when everything is still building up and small. Not a lot of preset huge kingdoms.
Start date: 1066
Spain is a good place for this. At the top left of spain there is Leon, Castille, and Galicia. These are actually rivaling brothers and I think father. It's a 3 way free for all for those 3. Unfortunately though they are not dukes. They are 3 kingdoms warring against each other to see which family member will rule. Along with some trouble from the southern foreigners that have a different religion.
