Did you try GNU Go? That should be hard enough for most beginners.
The problem with GNUgo is that it teaches a style that would not be effective in beating humans. Generally, you have to build up moderately difficult situations, where you have a deep sequence of forcing moves. These kind of deep but simple to prune trees are very easily read by humans, but GNUgo sucks at them, especially if they are on the interaction boundary of bigger fights.
Still it can be valuable learning tool, but one will learn a different skill set to playing with humans.
The problem with GNUgo is that it teaches a style that would not be effective in beating humans. Generally, you have to build up moderately difficult situations, where you have a deep sequence of forcing moves. These kind of deep but simple to prune trees are very easily read by humans, but GNUgo sucks at them, especially if they are on the interaction boundary of bigger fights.
Still it can be valuable learning tool, but one will learn a different skill set to playing with humans.