In my view, it's not multiple dispatch per se that is the bigger departure from traditional OOP, it's the fact that methods are no longer contained in the classes. Julia draws a separation between data (structs: the nouns) and behaviors (functions: the verbs). Traditional OOP never really made sense to me; why should each class define and own its own methods? It feels far more sensible to me to just have global behaviors that are well defined. Those verbs can sometimes apply to _anything_ (leaning on more rudimentary operations that you need to define; duck-typing), and sometimes they require you to explicitly define your behavior, and sometimes you just want to add an additional optimization that's available in your particular situation.
Once you have that mental model down, multiple dispatch is just how Julia chooses which method to call... and it's really not much different from single-dispatch.
State mutations. That's it. By ensuring that your data can only be mutated by a your API, it can never get "corrupted".
Bag of functions isn't a bad way to think about it, even for Julia. In some languages, only the name of the function determines which function is called. In others, the number of arguments is used too, so eg foo/1 and foo/2 may be different functions. In Julia, the types matter too, so foo(::Int) and foo(::String) are different functions ("methods" in Julia terminology), and which is used is based on the type of the argument, rather than the number.
That's where the magic in Julia happens, as if you define a function foo(x), without specifying any types, then the specific functions that foo call will only be determined once the type of the arguments to foo are known. But once they are known, that type information can ripple all the way down, picking up the specific implementation for each function depending on the actual types used.
The point is that simple concepts are nice to explain for a beginner, but what actually built your intuition in how to use objects is the years and years learning and experiencing it's benefits and pitfalls. With multiple dispatch it's the same, but since few languages use it (and even fewer, if any, pushes it everywhere like Julia does) most people didn't experience this process.
For me when I'm using a function I just consider them as self-contained abstractions over the arguments. For example there are hundreds of implementations of sum (+), which in practice I ignore and only think about the concept of addition no matter what arguments I give and I trust the compiler/library to find the optimal implementation of the concept or fail (meaning I have to write one myself). If I'm writing a method (or function) I consider arguments as whatever acts the way I need so that I can implement the the concept on them (for example if I'm writing a tensor sum I just consider arguments as n-dimensional iterable arrays and implement assuming that - and declare for the compiler when my method is applicable, without having to care about all other implementations of sum - if anyone needs a scalar sum them that person can implement it and through collaboration we all expand the concept of sum).
And the fact that whoever uses a function can abstract away the implementation, and whoever writes a function can abstract away the whole extension of the arguments (through both duck typing and the fact that the compiler will deal with choosing the correct implementation of the concept) means everything plays along fine without having to deal with details of each side.
Once that's understood, multiple dispatch is simply using all of a function's arguments inferred types to choose which method should be invoked.
I think it's a good mental model to constantly keep the types in mind, but I have made the experience that people working exclusively in dynamically typed languages, i.e. the majority of data scientists, don't share that mental model.