1.) Trägheitsmoment
Wenn du die Charaktere als Freunde oder Diener des Oberherrschers (Herzog, König, was auch immer) einführst, stehen die Chancen nach meiner Erfahrung nicht besonders hoch, dass sie sich von diesem jeweils ab- und irgendeinem anderen Adeligen zuwenden werden. Frei nach dem Motto "Mit dem haben wir gute Erfahrungen gemacht, warum sollten wir jetzt jenem trauen?". Das solltest du auf jeden Fall im Hinterkopf behalten und dich dementsprechend auch nicht davor scheuen, mal schlechtes Licht auf den initialen Verbündeten scheinen zu lassen, alleine um auch den Spielern auf einer Meta-Ebene klar zu machen, dass nicht zwangsläufig irgendeine Art von Treue verlangt wird.
2.) Größe
Daher meine Empfehlung, auf jeden Fall mindestens ein Herzogtum oder eine Markgrafschaft herzunehmen. Das bedeutet ja noch lange nicht, dass du alle Vasallen bis zum letzten Junker ausformulieren musst - dafür gibts ja Namensgeneratoren.
Schwierig. Dein Einwand ist berechtigt. Gleichzeitig finde ich eine Kampagne in einem ganzen Herzogtum wirklich zu groß um einen Konflikt zu erzeugen, in den die Charakter glaubwürdig involviert sind.
Am besten wäre vielleicht ein Mittelding. Die Spieler arbeiten offiziell nur für einen einfachen Grafen, sind aber auch in das Intrigenspiel in anderen Teilen des Herzogtums involviert. Oder sie sind in einem kleineren Herzogtum, wo es nicht all zu viele Grafschaften und Adelssippen gibt.