It seems like both can be used to define functions that you can implement later, with different data types. AFAIK the major difference is that defmulti works on maps and defprotocol works on records.
What other differences there? What are the benefits of using one over the other?
Short version: defmulti is much more flexible and general, while defprotocol performs better.
Slightly longer version:
defprotocol supports dispatch on type, which is like polymorphism in most mainstream programming languages.
defmulti is a more general mechanism where you can dispatch on other things than just a single type. This flexibility comes with a performance penalty.