We liked Chessmaster (we have an older version, "5500" I'm not sure what the latest version is.)
There are tutorials on the disc, and during play, you can ask the computer for advice about the best move to make. If you attempt to make an illegal move, a box pops up and explains why you can't do that. I don't know how this compares to other programs (do they all do these things?) But everyone in our family has played this and enjoyed it.
If you go to gamespot.com you can read reviews on various games.