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.
Das Ziel soll nicht sein den Herrscher zu stürzen oder zu bekämpfen. Es geht eher darum, wer die besten Plätze in der zweiten Reihe kriegt und da ist es kein Widerspruch wenn man offiziell für den Herzog arbeitet und gleichzeitig Privatfehden ausfechtet, vielleicht auch zu Ungunsten der Position des Regenten, aber nie direkt gegen ihn.
Die Position des Landesherrschers und auch eine gewisse Abhängigkeit von ihm gehört zur Grundaufstellung, aber darüber hinaus gibt es noch ganz viel nebenbei oder auch entgegenstehendes zu den Verpflichtungen beim Landesherrscher. Direkt an ihn gebunden sollen die Abenteurer aber nur sein, wenn sie das auch wollen.
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.