Developing believable virtual characters has been a subject of research in many fields including graphics, animations, artificial intelligence, and human-computer interaction. One challenge towards commoditizing the use of virtual humans is the ability to algorithmically construct characters of different stereotypes. In this paper, we present our efforts in designing virtual characters that can exhibit non-verbal behaviors to reflect varying degrees of warmth and competence, two personality traits shown to underlie social judgments and form stereotypical perception. To embark on developing a computational behavior model that portrays these traits, we adopt an iterative design methodology tuning the design using theory from theatre, animation and psychology, expert reviews, user testing and feedback. Using this process we were able to construct a set of virtual characters that portray variations of warmth and competence through combination of gestures, use of space, and gaze behaviors. In this paper we discuss the design methodology, the resultant system, and initial experiment results showing the promise of the model.