There are several ways to encode state machines. However, since a circuit is required to decode the next state and output, implementing a bigger state machine would possibly reduce fmax of a design anyway.
One way to deal with such an issue is to use a soft core to implement the state machine in software. However, having multiple softcore processors e.g Nios II may not be practical as well.
Now if it becomes clear that the design requires multiple state machines where each has maybe 10s of states, does this mean that the design must be simply implemented fully in software and not in hardware or techniques exist to implement multiple large state machines which also ensure that we get large fmax? How about one designing a very basic processor that can only do basic arithmetic logic operations and write a short program that goes into a hard memory block? This adds the complexity in that debugging the assembly type code will be another new issue to deal with.