1. Other than combat, what are (or should be) the advantages of having a party? What would be a good reason not to solo?
Access to various social circles that are not available to you without a specific party member, which brings in its own opportunities for side quests or even more insight into any quest itself, including the main quest. Imagine that you learn more about a quest, may even be main quest, thanks to one of the characters in your party who introduced you to different characters who know different things, which in turn may affect the direction you'd like to take in regards to main quest / any quest. Beyond being a trivial tool for Bethesda type "good at everything" gameplay (more on that below), party members are invaluable social tools.
Beyond individual character skills, party members can offer more paths to solve quests, available again through their own social circles. A certain quest for which you'd need to break in to a specific place may suddenly become easier because you have a party member associated with certain characters related to the quest. He knows someone who knows someone etc. and now you have an easier way into the place, whereas another quest might be more difficult than it would be because of the same character.
Likewise, a character may insist that they visit his mother who (s)he heard is in deathbed, where you can make a judgement call to agree, disagree and kick his ass, disagree but tell him to come back when he's ok or disagree and persuade him that she will be dead by the time (s)he goes and the current task at hand is more important (all of which may come back to bite you in the ass or help you at some point in future).
Social baggages character might carry is the best excuse to have a party in my opinion.
Party dynamics - your thoughts and ideas.
A game mechanic where your character can statistically benefit (or get hampered) from social interaction maybe. For instance, in an imaginary character creation that's like a cross between Fallout and Daggerfall and can choose perks such as "loner" or "people person" which could determine certain predispositions for certain skills in regards to the party members, you may have a character that's dependant on others' presence around himself/herself for most efficient use of his/her own abilities and vice versa.
If having party members won't bring their own negatives in addition to the benefits, much like balancing your character in creation with tags in Fallout or advantages/disadvantages in Daggerfall, the party mechanic itself becomes usually trivial. The most common and usually the inevitable setup that is one guy that does fighting, one guy that does magic, one that steals and picks locks and one talker, isn't much difference than becoming master of everything in games like Morrowind or Oblivion. You still get to have access to all different fields and then the only meaning of having part members is the ability to carry more and their individual ability to leave the party or die, but then again, you can usually find replacements. To me, that's not enough of an excuse to have party members.
There may even be a general predisposition for sociality of the character that's based on things like, I don't know, how often the characters talk? Things they say when they talk? Their social circles? (I certainly wouldn't like to befriend a junkie who attracts other junkies). Whether a certain character is more of a statistical benefit or negative to your own abilties would become more clear as you spend more time with that character, while the effects of the positive and negative sides would also become more observable (increasing modifiers for the effects) with the time. That could provide you the in game perception to draw a line somewhere or stick to a character, and it might also make it more important to stick to a characters. Obviously, if a certain character helps bring the best out of you, why part with him/her? Likewise, you could care more about the death or ill condition of such a character. I certainly didn't give a shit about Imoen in either Baldur's Gate games when she was ever in a critical condition. I certainly wouldn't change my route, my gameplan just because the bitch would die or died but can be ressurrected. But if she provided benefits to my character's own efficiency beyond her own skills, I certainly would.
However, some social skills like manipulation and what not, should enable you to withstand/negate negative effects so you can play the weasel in a party, or manipulate and use characters like tools until you no longer need. A little more on this as a reply to the 4th question.
The same kind of mechanics should be present between other characters as well. You may have two characters in your party that you like to keep but they hardly cope with each other. A party member might be bothered by the social circle of another member. "He always attracts junkies, so I say we kick his ass".
Party members' ability to double-cross you about certain things or turn on you instead of a bitchy "I'm leaving", because you ignored all the warning signs, or even do things behind you and dump you when you need him/her the most. If the recruitable characters are to be designed with their own proper social circles, their place and relations in those circles, and all these circles' standing with each other, incredible gameplay options could emerge (emerge not as in "totally unplanned", but rather "completely unexpected by the PC").
Another interesting mechanic might be manipulating other party members yourself. A little on this below.
Ah, also, in-party talk, though that's nothing new I guess. Whenever you meet someone new, go to a new place, etc. party members can comment on it, say "there's no fucking way I'm crossing this rotting bridge". BUT, we need even more input from them. For instance, they could comment on and suggest travel options in a travel map, suggest alternate routes, give you info about surroundings (though that would depend on the nature of the travel map).
4. Leadership - should you always be the leader or would you, the player, be ok if someone else takes over and tell you "listen, pal, we've talked and decided to go to town X. You're welcome to tag alone, but we aint going to Y at the moment. If you need us, you know where to find us". What about being challenged for the right to lead? Party members voting for or against certain quests?
In addition to that, ability to "conquer" party members one by one might be nice. You join them, based on the "company" predispositions I described above, you get to befriend them, gain their trust, manipulate them around and persuade them into your own agenda. Really, having a party shouldn't just mean having sidekicks to compensate for where you fail, but as story or other gameplay devices as well. If there are many characters who you could party with, and various bands of adventurers where a specific one with their own specific goals and agendas might prove useful to you either in siding with them or in leading them do their doom, then why not do it? Hell, joining a party just to lead them to their doom could even be a quest!
5. What's a good party member? What qualities/traits/contributions would you expect from such an individual?
One that has a meaningful social standing that will effect you for siding with him/her. "Geez, I can't believe Vince befriended that pedophile!". "Oh my fucking god, Vince is dating the hottest girl in the school, he's gotta be so cool".
