As Fox, you actually have the advantage in this matchup, but only if you play it correctly. Zelda has a brutal punish game on spacies (chain Uthrows into Usmashes into Nair or Kick) so a reckless approach can mean instant death for you. Fortunately, as Fox, you can dictate the pace of the match and have total control over when you go in. Zelda cannot out-camp you because she loses to both laser camping and DD camping. This means she either has to play the neutral along with you (which you will eventually win), or she must approach on your terms. If Zelda shields a lot, you can pressure with Nair shines, which she cannot shield grab. Make sure your spacing and timing are on point though, because she will not hesitate to shield grab or kick/Usmash OoS given the opportunity. Zelda is not knocked down by shine and she has high traction, so you can repeatedly waveshine her across the stage and end it with a shine spike offstage or Usmash. Uthrow -> Uair will not work on Zelda at higher percents, so you will need to rely on Usmash for most kills. If she ends up in the air, however, chasing her down with Uairs and trying to juggle her is not a bad idea, since she's not good at coming down from heights. Make sure you mix up your recovery; Zelda has a strong edgeguarding toolkit and a good read on your recovery will likely result in a KO.
As far as stages go, avoid FD like the plague, since she can kill you off of a single grab. Fountain, Green Hill Zone, and Dreamland also favor her. Try to find large stages with plenty of room for camping, small top blastzones, and enough platforms to avoid her combos. PS2, Lylat (no, seriously, it's great for you in this matchup) and Yoshi's Island (Brawl) are fantastic for you. Smaller stages like WarioWare and Yoshi's Story are tossups, because you kill her very easily off the top with Usmash or Uair, but she also kills you earlier with kicks.
However, the best advice I can give is to be patient; Zelda gets her strongest punishes off of unsafe aggression. Don't commit too hard unless you can confirm a hit, and only move in when you are certain that she is committed to an option.