One of the greatest features of FFVI is its large cast of memorable characters. However, one of the downsides of this is that most of the characters don't interact much with one another. The following is a list of all of the recruitable characters in the game, a bit about each of their personalities, and some speculation as to how they would get along with Shadow.
It's a common misconception that Terra is the "hero" or "main character" of FFVI because she is the first character you can control. While much of the plot depends upon her, there are other characters that are just as necessary to the plot. That being said, most of Terra's storyline focuses on her struggle to find who she is, and once she does, she struggles to figure out what love is -- whether it be familial, romantic, or otherwise.
Interaction: Just because Terra is one of the main characters doesn't mean that Shadow interacts with her a lot. However, there is one notable scene between the two on the boat to Crescent Island -- Shadow overhears a conversation between Leo and Terra about what love is, and he tells her to look within for answers. It is a surprisingly touching scene.
Even if Locke would rip your lungs out if you compared him to Robin Hood, it's hard to deny that he resembles the Prince of Thieves in more way than one. Locke is a refreshing break from angsty Final Fantasy leading males -- instead of brooding, he cracks jokes. However, don't let his lighthearted exterior fool you -- there is a sizeable backstory to this fun-loving treasure hunter...
Interaction: There is surprisingly little interaction between Shadow and Locke, despite the fact that Locke is the leading male of the game. The only notable scene between the two is when they are on the boat to Thamasa and Shadow witnesses Locke engaging in some... slightly sketchy behavior. Even though there is little interaction between the two, they are pretty obvious foils for one another, given their similar backstories and opposing personalities.
Edgar Roni Figaro
As the King of Figaro, one would assume that Edgar is stern and proper. Well then one would assume wrong! Edgar doesn't think twice before having a little fun, and he certainly doesn't have any qualms hitting on the ladies. Even though it might seem like he is not well-suited for being a king, Edgar looks out for his kingdom by joining the Returners in an attempt to prevent the Empire from taking over Figaro and the rest of the world.
Interaction: It is interesting that Edgar is the first person to say anything about Shadow -- he is the one who makes the comment that Shadow would "slit his mama's throat for a nickel." Perhaps Shadow was a well-known assassin in the Kingdom of Figaro. Beyond that, there is little to no interaction between the two. Too bad!
Sabin Rene Figaro
Sabin is the younger brother of Edgar, but you wouldn't be able to tell at first glance. Sabin is everything that Edgar is not: muscular, informal and reclusive. While he is not as central to the story as his older brother, it is interesting to watch his relationship with his brother evolve throughout the game. Sabin also provides a fair share of comic relief.
Interaction: Oddly enough, Sabin is the first character we really see Shadow talking to (unless you count Interceptor). Sabin asks Shadow how to get to Narshe after he gets separated from the rest of the party, and Shadow offers to show him the way. He also warns Sabin that he will leave him whenever he sees fit. Besides this initial meeting, the two do not interact much. It seems that their dialogue is just meant to explain how Shadow becomes involved with the party in the first place, and not much beyond that.
In a world of helpless lead female characters, Celes proves that not all women are totally helpless and useless in battle. As a former general for the Empire, Celes was infused with magic, thus making her a magitek knight. She is imprisoned after being accused of treason by the Empire, and Locke stumbles upon her by chance and rescues her. Even though Celes is pretty self-sufficient and tough, she is not above giving into her emotions from time to time.
Interaction: I honestly cannot think of a time when Shadow and Celes engage in dialogue. My guess is that they appreciated each other's assistance, but when it came down to it, they didn't really feel the need to share their appreciation with one another. One similarity they have is that they both were formerly associated with the Empire.
Cyan is a classic example of a chivalrous knight, and with his overly proper speech, he doesn't let you forget it! Despite tragedy in his life, Cyan keeps a positive outlook and joins the party in an effort to put an end to the Empire that has caused him so much pain. He is one of your party's most valuable fighters, even if he isn't one of the most important characters to the plot.
Interaction: Shadow and Cyan get to know each other when Shadow and Sabin reach Doma Castle and join forces with him in order to fight off the Empire. However, all of the dialogue is between Cyan and Sabin, so there is not much evidence that Cyan and Shadow have a relationship. They both are extremely powerful fighters, so at least they have that in common.
Wild child is an understatement. Gau was brought up with the wild beasts of the Veldt, and as a result, he can mimic the attack of just about any monster. This is pretty useful if you can master it! Sabin encounters Gau on the Veldt and is able to lure him to help him by presenting him with dried meat. Although you don't get to see much of Gau's story, he has very a touching theme song, which leads you to believe that he's a sweet kid.
Interaction: Umm, yeah right. I doubt Shadow had any patience for Gau.
Setzer is the millionaire of the Final Fantasy VI world, and consequently, he is the only civilian who has his own airship. Even if the party has to deal with him trying to abduct Celes at first, they get past that pretty quickly once they realize that an alliance with Setzer means access to his airship. Setzer is one of the more entertaining memebers of the party, but like Shadow, he has a dark past that he keeps mostly to himself.
Interaction: Surprise, surprise -- Shadow doesn't really interact with Setzer. It's unfortunate, because I think these two would have a unique dynamic. They're both pretty into making money, and they're both dark and brooding.
I don't know if you can make a Final Fantasy game without the obligatory cute, little girl. Relm is that girl in Final Fantasy VI, and her theme song doesn't let you forget it. She is quite the artist -- in fact, she can sketch monsters so well that the sketches will come to life and replicate the skills of that monster. At any rate, Relm lives with her grandfather, Strago, and it's unclear what has happened to her parents...
Interaction: Relm and Shadow have a very cute, but subtle relationship. Interceptor seems to be quite taken with her (wow, he doesn't want to eat her? She's even small!), so this causes Shadow to have more run-ins with her than he would like. Shadow ends up saving Relm from a burning house after Interceptor goes chasing after her. He claims he only wanted his dog back, but...
Just as how every Final Fantasy game needs a little girl, every one also needs an eccentric old man (or at least the earlier Final Fantasies). Strago is the endearing, magic-using grandfather of Relm, and his knowledge of magic and espers turns out to be quite useful to the party. He is one of the last characters that your party acquires, so he does not get much time to interact with everyone, but it is clear that he loves his granddaughter. He's also a bit hipper than your average grandfather... I mean, he's out fighting battles!
Interaction: Strago and Shadow do not interact much other than the occasional exchange about how odd it is that Interceptor and Relm get along so well. Strago is pretty snarky, so it would be funny to hear what he would have to say about Shadow.
Mog, Umaro & Gogo
These three characters are all optional members of your party, thus they do not have any significance to the plot (nor do they ever interact with Shadow). But I thought they deserved an honorable mention!