Pathfinding can very processor intensive and is best threaded out, or at least limitted by how many nodes/arcs are processed at one time.

Pathfinding is not really a good state to use. States could be, waiting, walking, fighting... an enity might change state from waiting to walking because of a result from the pathfinding algorithm, for example.

Which still leaves you with the problem of what if an entity changes state while it is still searching for a path (or other critical function)? When the pathfinding (or other critcal function) completes, it sends a message to the affected/ calling entity and the entity then decides what to do with it depending on the state it is in at that time. If changing state means that the pathfinding is no longer relevant, a request to stop searching can be sent. By sending messages between objects, everything can run autonomously. For your animation problem, you don't neccessarily have to stay in the same state because an animation is playing. If you are halfway through a run animation and your player switches to walk, have the walk state begin the walk animation from when the run animation reaches its keyframe.

Fuzzy logic is good if you want it possible for your entity to be in more than one state at any time. For example, in a state of GoingForPowerUp while ShootingTheCrapOutOfEverythingInSight.