shopkeepers already yell about their wares: "buy your large mail shirts here" etc. Doing that with other requests "hey, would you like to join my party" would work, I think. however, the idea of being recruited by an NPC so that you can travel as their companion seems like it would be difficult to implement.
Perhaps although what if the party system had something added where other characters would occasionally give suggestions, such as (if you're in a very dangerous area) "I don't like this, let's get out of here" or the like, and there's a chance that even without the player's consent they will go do whatever it is, fleeing being only one example.
I'd been briefly thinking about it. Maybe party members are given an own goal, or a list of goals, like:
-Don't get killed
-Get your father's copper sword back
-Kill evil bandit leader who killed your father.
The last one could mighty well be a goal hared by all party members. The second one would only come into play when the player adventurer tries to sell that copper sword. Suddenly your party member becomes hostile.
Finally, the first one would be the cause of the party member running away or persuading you to stay away from dangerous places.
The player should be able to get information on these goals from the party member by conversing with them. You could even have goals that are hidden and the party member won't tell them to you for no reason(unless, maybe you are good buddies or something).
Similarly, there's a lot to be done with a conversation system. You could have a list of terms that the player comes across, talking to npcs, which they can then use to interrogate other npcs with. Hell, you can even ask your party members those things, and then they'll tell you they may have been born in that city you are asking about.
And then there's the idea of personalised conversation, where the speech is changed by the personality traits of the person in question. But that's all pipedreams.
As for the cheese maker problem, the disposition seems smart enough of a way to deal with it. Otherwise, you can always attempt disguising yourself as a beggar.