How about these as options (both implemented as some kind of point-click adventure)...
a) Break down the story and have the player have to say the right things at the right parts. If he doesn't, something funny (and usually painful) happens down the line. It may not be immediately afterward, so for example (if the player knows the play) and MacBeth asked the wrong questions of the witches for example, he might not be warned, "Beware the ides of March!" and so he gets axed at some inopportune moment because he's out playing croquet on the ides of March... or something like that. You get the idea.
b) Have the story play through linearly. But insert extra bits in between parts of the actual story, things that might have happened to the main character(s), and play those bits out. interactively. So for example after some speech in Othello, he's ravenously hungry and you have to help him find the kitchens or he comes to an ignoble end.
Traditional stories are linear, that's why they tend not to translate too well to an interactive experience. It's the interactiveness that makes things fun. However, the best value you're going to get from Shakespeare's plays comes from his excellent stories and characters. Basically if you view a story as a linear sequence of events i.e. a linear graph, then in case (a) you are allowing branchings in that graph, but those branchings immediately lead to a cut scene detailing the consequences of failure (i.e. of choosing the wrong action). Whereas with (b), you are lengthening the graph by inserting extra "pieces" of interactive story in between the main (and mandatory) parts of the graph. In this latter case, wrong choices need not be fatal, they can just be for fun, because it doesn't affect the outcomes of each part of the main storyline.