Aside from Encyclopedia himself, the other two common characters are his partner, Sally Kimball; and their nemesis, Bugs Meany. Encyclopedia's father (Chief Brown) also makes an appearance quite often. He's the chief of police so he occasionally provides aid from the proper authorities, but more often his role in the plot is to present Encyclopedia with the sorts of cases that wouldn't usually come to the attention of a 10 year old.
In particular, Sally Kimball is an interesting character, especially in light of modern feminist literary theory. There are a few troublesome aspects to the character and her role in the series, but I believe overall she is an intelligent and competent role model for girls today (or anyone else, for that matter).
She's presented as Encyclopedia's junior partner (not his secretary or "personal assistant"), but the "junior" is usually emphasized; Encyclopedia makes the decisions and Sally follows along. The series makes it fairly clear that this is because Encyclopedia started the agency and has more experience as an investigator, but some might find it objectionable that the lead female character is subservient to the lead male character.
Her main role in the partnership, however, is that of the "muscle". She's mainly there to keep Encyclopedia from constantly getting beat up for being a smart aleck. Bugs Meany, in particular, would love to give Encyclopedia a sound thrashing, but is clearly frightened by Sally. This is quite reasonable; girls usually get a growth spurt a tad before boys do; I suspect a good number of fifth grade girls could beat up all the boys in their class. Still, it's interesting that the male protagonist is not especially interested in athletics, while the female protagonist is. This is a refreshing escape from normal gender roles (especially in children's literature). And while the series is mainly a celebration of intelligence, Encyclopedia quite often needs Sally's help when there is something to be done that requires strength or agility.
Still, if Sally is the "brawn" of the partnership, that means Encyclopedia is the "brain". Her most common role in dialog is to serve as a Watson to Encyclopedia's Holmes. This means she often asks kinda dumbs questions for him to answer; compared to him she sometimes appears less-then-bright. Of course, everyone in the series appears less-then-bright when compared to Encyclopedia. It's just that she spends more time with Encyclopedia then anyone else, so you notice it more with her. She's probably the second most intelligent character in the series, but she dosn't get to shine very often in this respect.
Sobol partially alleviates this problem, but presents another, by having occasional episodes where Sally solves the case. On one hand, this is great because Encyclopedia is right an insufferable amount of time, and it's nice to see someone else get the glory for a change. On the other, these cases almost invariably involve "girly" things, such as fashion or relationships (Sally, for example, notices that a Woman's shirt buttons the oppose of a man's). Encyclopedia has a lot of books smarts but isn't so good at fathoming emotions. This would be an interesting comment on how different people have different types of intelligence, except Sally's attitude is usually, "I'm a girl, so I know these things." This is undoubtedly better for Encyclopedia's ego, but it's kinda unfair both to girls who don't know these things, and to guys who do.
Worst of all, Sally's other epitaph (aside from "junior partner" and "took down Bugs Meany with one punch") is "prettiest girl in fifth grade." Which is fine, expect we rarely get an assessment of any of the male character's looks. We don't know if Encyclopedia is cute or if Bugs is studly. I'm sure making Sally pretty makes her more popular amongst the largely 10-year old boy audience (not to mention pedophiles), but I'm afraid the message here is "if you're a girl, looks are important..." after which it's all too easy to conclude, "...because looks are all a girl has to offer".
Still, Sally clearly does have more to offer then looks. She's strong and smart (as mentioned, she's probably the second smartest character in the series; and she's the only one to occasionally get the better of Encyclopedia). Better yet, in many ways she's a more accessible character then Encyclopedia (even for male readers). He's freaky smart, to a point that many ten year olds can't relate, while Sally is intelligent but still human. He may be the driving force of the plot, but he's oddly uncharacterized. She actually gets more personality development then him. This might make him easier to identify with, but she's more likable.
Or maybe I just like her because I was about 10 when I first read the series, and she was "...the prettiest girl in fifth grade, and the toughest too".