Indeed, MAME is always a good way to get them into games. Outside that look for some of the arcade style puzzlers for the PC itself like Mr. Driller or Bust-A-Move.
Also the Lucas Arts games always go down really good. Grim Fandango, Day Of The Tentacle, Moneky Island series and especially Sam N’ Max are all good choices.