Tragedy, Comedy, Satire, You Name It
If you want to figure out this play's genre, don't even think about trying to pin it down to one specific category. Trust us. It's impossible because Troilus and Cressida is a mishmash of tragedy, comedy, and satire.
To make things even more complicated, the play is based on Chaucer's courtly romance Troilus and Criseyde and Homer's heroic epic The Iliad, so it's got some of those elements, too. Although, we should point out that Shakespeare spends most of his time bagging on the kinds of stuff we see in courtly romance and epic literature. When it comes to genre, Troilus and Cressida is the Frankenstein's Monster of literature.
That's why a famous 19th century literary critic named F.S. Boas argued that Troilus and Cressida (along with Measure for Measure and All's Well That Ends Well), deserves its own special category: "Problem Play." Basically, a problem play is a drama that isn't quite a comedy (even though it may have some comical tones) and isn't quite a tragedy (even though it often seems like one) (source).
Of course, Troilus and Cressida can also be considered a satire. That's because it uses a lot of sarcasm, wit, humor, and irony to criticize humanity. Can't get enough satire? Check out "Tone" for more on this.