There are two kinds of games:
The kind that uses real people as the social power, and the kind that uses fake people as the social power.
There's a big difference. A fundamental difference that most designers don't seem to understand.
See, multiplayer games such as Starcraft, Settlers of Catan, or even Apples to Apples, they use one tactic to bring players together: direct in-game effect.
You like or hate Sue because Sue just played in your favor or against it. You and Sue might gang up on George, and you'll like Sue depending on how well she helps in your campaign against the evil menace that is George.
Recently, single-player (and single-player portions of multi-player) games have decided this is the best way to make an artificial friend for you in a game. By giving that person an in-game effect.
What they have forgotten is that if Sue blocks off the thoroughfare with a spawning pit, we get really irritated with Sue. Being part of a team requires that you feel the other members are pulling their weight. If they aren't maybe we can yell them into straightening up... but even if we can, we're still irritated with them.
Can you create an AI for your game which won't ever get in the player's way? What's that, you're introducing the would-be friend with a mission to save him? Wrong answer!
Really, "Hound Dog" is an excellent way to keep this in mind. "You ain't nothin' but a hound dog, cryin' all the time." Is this your character? Change it. "You ain't never caught a rabbit and you ain't no friend of mine!" Your AI doesn't work well? Don't put a character in a situation where they have to use it.
Okay, to laser in here, there is precisely one way to put friends in games:
Steal from movies.
I rarely suggest this. Games and movies are deeply different. But in this case, movies know how to make friends. The AI for games can't hold a match to it except in very rare situations. Even if it can, using movie techniques as well can't hurt!
Friends in movies are made primarily with three techniques, as far as I can tell: hang-out, support, and history. In a movie, Alex and Frank are friends. How do we show that?
Well, usually we use dialogue. We show Alex and Frank hanging out when there is no need for them to. Alex isn't rescuing Frank, and Frank isn't helping Alex fight off a horde of exploding demon zombies from St. Louise. No, they're spending time together because they just want to.
Sure, you have to be careful not to bore your players with hanging-out cutscenes. But I'm sure a clever person like you can work out a way to do that. ;)
Support is more straight-forward and often applicable to games. To show Alex and Frank are friends, maybe Alex loans Frank fifty, or maybe Frank advises Alex on his girlfriend. This shows the meat, the reliability, of their relationship. This can be done really easily in a game. It's rare that I feel as much friendship with a clumsy AI character as I do with a character that simply gives me a new gun every level.
Of course, this support needs to be useful. That means that the tutorial guy is usually irritating, because he says useless things. This takes up your time and presumes you're an idiot. Similarly, if I already have Excalibur, having someone give me "Steel Longsword + 1" isn't going to make me feel like they've helped me at all.
The last technique is history. And here is where the interesting and unexplored section of the idea lies.
In movies, history is shown through either dialogue or random stuff like photographs. We show that these people have been together for a while. They've been through stuff. Alex says, "Just like that time when..." and Frank says, "She looks just like Tilly..."
This can be done pretty easily in games, too, of course. The interesting way to do it is to tie it in to the game mechanics.
If you have team mechanics which obviously change over time, you can use those. For example, if your game has dual techs, give two friends great starting dual techs. If your game uses a gunner/pilot system, make your best friend be awesome with you in the other role.
However, if you don't have any such thing, you can still tie it in with game mechanics by tying it in with support.
The main character, Alex, is going out to fight exploding demon zombies from St. Louise. Frank says, "Hey, Alex, I've still got that sword we made in shop class, if you want it." Frank doesn't just give Alex the sword: he establishes a history.
Similarly, if Alex and Frank have a cut scene where they do something cool, there's no need to have them talk it over in length. They're old friends. They know how they think. Alex says, "We need to -" and Frank says, "Yeah, I know. Ready?"
Once you have made a friend, there are lots of things you can do with them to make the player react. But that is another, even longer, essay. Enemies are also a fun topic for another day...
Lots to do!