As I said, I'm going to roll some random connections as inspiration. You're welcome to use or disregard these as you see fit; I think preexisting connections are fun, but some people don't like them, preferring to let relationships emerge organically, which is perfectly reasonable.
The method I'm using, which I came up with off the top of my head, is to roll a d6 to determine an ability score: that defines the sort of connection, relationship, or event between the characters. Then a d4, to determine whether the connection is strongly negative, slightly negative, slightly positive or strongly positive.
Trees Glūm: With Glanduk, Intelligence, strongly negative. Perhaps the hobgoblin bested you in a battle of wits, made you feel foolish with his superior book-learnin' or tricked you with some false fact?
Glanduk: With Milo, Strength, slightly negative. Did the brawny halfling outdo you in a brawl or athletic contest in which you were competing (sort of a Gimli-Legolas rivalry), or does your hobgoblin pride rankle at being outshone by someone half your size?
Milo: With Thatch, Dexterity, slightly negative. Does the half-orcs clumsiness grate on you? Did he stumble and crash through the undergrowth while you were sneaking up on some prey? Do you wish you could show him how to enhance his physical might with some agility and grace?
Thatch: With Trees, Dexterity, slightly positive. Both Thatch and Trees are pretty clumsy. is this a source of commiseration between them? Or more abstractly, as a fellow foreigner does Thatch admire Trees' extensive travels and wandering feet?