Full Wormage or Rowy Madness with delays first to introduce them to all of the weapons, then:
If they like rope more than anything, play Shopper
otherwise, play Intermediate
EDIT1: Omg, haven't read the OP in the first place. Try Normal but with less turn time maybe? Problem with them is that they don't realise that this is a turn-based S T R A T E G Y game. civ 5 plz