In OO terms, I’m talking about having N classes—which for the sake of argument are not related by inheritance—one interface, and M functions implemented in terms of that interface. Clearly it’s cheaper to implement the interface once for each class than to implement each function for each class.

That part has nothing to do with monads. The advantage of monads is the actual functionality they provide, of first-class effects and easy EDSL creation.