How about Mini Chess? The rules are the same as standard chess (though I think I've seen a version where the pawns can't move 2 places at once when on first row) it's just the board that's smaller.
Anyway, should provide some faster games and I'm sure many begginers would be more inclined to play this smaller version.
And from my limited experience it's a good battle ground to train on How-to-avoid-a-stalemate-when-you-have-a-sure-win kind of games :)