The difference between an "easy" and a "hard" sudoku (and other problems of that ilk) is essentially how many steps ahead you need to think in order to derive useful information.

An "easy" sudoku is one solvable by mechanical application of the rules of the game - if there's only number that can be placed in a cell, fill it in, and similarly if there's only one cell in a given row, column, or box that a given number fits in, fill it in there.

As things get harder, other logical steps are required. For example, if there are two cells in a line, and both of them can only accept the numbers 5 and 9, you can conclusively say that no other cell in that line can be a 5 or a 9. That's looking one step ahead, and (depending on how often it's necessary) makes for a medium-difficulty puzzle.

As you move up difficulties things get more complex, and thinking several steps ahead becomes necessary if you want to make meaningful headway.

--

I would expect the "hardest" sudoku would not be one that's only solvable by brute force - that's a rather uninteresting puzzle, for a start. Instead, the hardest (in my opinion) would be one that requires making the trickiest insights in order to make headway without resorting to guess-and-check style exhaustive search.