I would just say to make sure you play the spacing game. As good as FAir spam is, it can't compete with a spot dodge grab with a fast character. use the needles to keep him at bay and if you find he's getting too close to you, try for the spot dodge, and follow up with a grab and attempt to combo him once or twice away.
...another defense that may work...Ducking. sheik's crouch is INSANELY LOW, and her d-tilt isn't that bad. if you find the FAir spam difficult to avoid, duck under it, dtilt when he's close and then combo him with an aerial neutral. personally, when playing Marth, I find it hard to FAir spam shorter characters...this may prove to be a good defense for the first few FAirs if you're looking for a way to break his momentum...just be carefully not to depend on it too much, because it can be rather punishable by his FSmash or DAir.
,besides that, I agree with the person above, Defense and Evasion. Hit and run tactics to get him high in damage, and if you're having trouble killing him off, Hey, how about this.... Knock him away off the edge, then Transform into Zelda and Din's Fire spam him. That strategy may or may not work, but it has served me well from time to time when it seems I'm just not able to finish them off with Sheik.
