I see, where you're coming from, but in that particular case, the "intuitive" explanation (walk on a graph) is far less intuitive for me than the proper explanation, that a Markov process is memoryless. That said, I used MCMC in the past to do physics simulation, where the Markov property also applies to the underlying physical process. So maybe it's just me.
No single explanation works for most. That's why you need multiple ways to explain things and how the standard education system fails at disseminating information.