The evil really is shared mutable state. In single-threaded case, shared mutable state means that functions cannot be safely composed - because one call can modify some state which is then read by a second call and so you'll get unexpected results. In multi-threaded case, shared mutable state means that you have potential for race conditions.
Functional programming generally avoids mutation. Functions can still share some state (e.g. closure can capture a state), but it cannot be mutated. In single-threaded case, there is also no non-determinism. In multi-threaded case, pretty much the only thing that you can do in pure functional style is to do fork-join parallelism (and data-parallelism) which does not need mutable state and is fully deterministic.
Agent-based programming also avoids shared mutable state, but in a different way. You have isolated agents that can only share immutable messages. So there is some non-determinism (because they communicate by sending messages), but they only exchange immutable values. In fact, you can even use mutable state inside an agent - as long as it is not shared, you still avoid shared mutable state.
