Since solving mazes is however (also) something to be enjoyed by humans, it’s possible that perceived maze difficulty could be dependent on factors that wouldn’t really matter for a straightforward algorithm. For example, a very “jagged” maze could feel more difficult for humans because it’s harder to follow with your gaze, while an optimal maze solution finding algorithm wouldn’t be impacted.
In cases like this, formulating difficulty can be more of an art than an optimization problem.
EDIT: See also andrew_eu’s reply (which I only saw now), where multiple “interesting” notions of “difficulty” are proposed.
EDIT: Relatedly, humans use heuristics a lot. And there are many NP-hard problems where we can solve lots of “reasonable” points in the problem space in reasonable time (computers or humans alike), at the risk of having to time out, maybe try with another approach, and eventually just give up. Traveling salesmen are actually traveling the country after all. So worst case is not always a good measure for games. But I see you mentioned that already.