Starcraft. It has the high branching factor of Go, the nonlocal nature of Shogi (being able to call in units to different places instantaneously), and the uncertainty aspect of Poker. There has been quite a bit of AI research over the past few years (particularly at Berkeley and Stanford) by top researchers, and best bots results are honestly quite weak.
It is probably possible for a computer program to win by using abusive micro tactics that take tens of thousands of actions per minute. However this is just exploiting a single weakness of humans, so a more fair comparison would to limit a computer program to the most actions per minute that a top human can execute, say 500 APM. In that case I wouldn't be surprised if the problem is harder than Go.