To followup on what johnthedm said... You could also set some sort of destiny/clan mechanic. Same homeland? do you hate the clan the other is from? Would you die for them, try to kill them. and all of this can be done at the table; So Bob picks the Dark Kingdom of Agather and so does Steph. Later in the process Bob is a noble steph a recently freed slave.. So the Destiny says they have to come up with why they are on this journey together. They dont like each other, want each other dead? or one secertly desires the other? or they have both sworn to do something to help both their families... Character depth created, by choice. That gets you buy in and that makes a huge difference in such situations.