In a piece entitled "With Friends Like These...", Games On Net profiles some of the most memorable companions we've adventured with across Black Isle and BioWare's catalogue of RPGs, including Fallout's Dogmeat, Baldur's Gate's Minsc and Boo, Planescape: Torment's Morte, Star Wars: KotOR's HK-47, Mass Effect 2's Mordin Sollus, and a handful of others.
If we're going chronologically, next would have to be Morte, the cynical floating skull from the greatest RPG of all time, Planescape: Torment, Morte. He was at the time, and still remains, one of the most interestingly written characters in the genre. Sure, he's a wisecracking talking skull who follows around a partially mummified immortal amnesiac, but that doesn't stop him from being a totally believable character, with motivations that are far greater than delivering the next one liner. Hell, pretty much the same can be said about all of the companions in Planescape: Torment, from Falls-From-Grace, the chaste succubus intellectual brothel owner, to Nordom, the rogue polygon from a plane of mechanical law. Each of them has their own goals and beliefs and more importantly, they are internally consistent. Their actions and opinions follow the rules of their character, not the rules of the player.
Mordin and HK-47 are all what I like to refer to as pragmatist companions. Their personality is set to (what is the most expedient course of action), and this is the trait that makes these three so compelling. HK-47 is the most deliberately pragmatic or the characters. He is an assassin droid, so his first solution to any problem is killing it. It makes for some incredibly funny dialogue, but what makes it so funny is that it's believable. It's not just some character that likes insulting meat bags and talking about killing things; it's a character that truly believes.