What kind of work has there been on creating programming paradigms that make it easy to both add new types and new methods? Is it a CAP-theorem-type problem where every solution is a trade-off, or is there a way to have your cake and eat it too?
That said, there is a complexity and readability trade-off (that is hard to quantify) because these more flexible programming patterns that can solve the expression problem are more complicated than plain method dispatching or switch statements.
For example, if I'm writing a normal Java class, I know where I go to find methods dealing specifically with instances Foo (namely Foo and its children and direct users); with multimethods, it's more likely that there is some multimethod out there in an unrelated class that looks for instances of Foo.
A very good summary of that paper is available here: http://lambda-the-ultimate.org/node/1518#comment-17566
Another alternative based on recursive modules: http://www.math.nagoya-u.ac.jp/~garrigue/papers/#privaterows