A companion that is integrated into a story where they play a role. They have a logic for existing, for accompanying the player, and an equally strong if not stronger logic for staying on with the player once their story is resolved. Most companions should actually be temporary, and no game that I have played has worked them into a narrative in a believable or disbelief-suspending way. They are usually presented as thinly veiled mechanical helpers, pack wagons, ego massages, or some mixture of all the above.
Agreed, but why stop there? I'd say the most interesting companions would be those who actively alter how the story/quests/encounters play out. Joshua Graham in Van Buren comes to mind as a rather emphatic example.
Also I'd say companions resistant to psychoanalysis/-therapy are interesting, the kind who won't let their entire personality be subverted by a few conversations and a resolution of a deep, dark secret from their past. Generally the kind that don't "know" they are a companion to a protagonist, but their own person with their own shit going on.