lol sheik. I go fox. I hate sheik, i always **** up combos against her.
Also thumbs, mute city is a horrible idea. It's already easy to deal with sheik's recovery, mute city won't change much. Falcon on the other hand, won't have a ledge to go for, which he can either grab or tech off of if dsmashed.
Really all you can do against sheik is space nairs and stuff until she screws up, and grab her, then do stuff out of that. Use platforms as much as possible to avoid needles and still approach.
If you're getting tech chased by a real pro, i'd say you have to basically just go for the edge. Like, if you get grabbed at a really low percent, DI out and tech towards the edge, and then try to edge cancel the next throw/just get throw off. You'll hopefully be at a low enough percent that you can be smart and snag the edge. What you do after that is your problem, but it's better than getting tech chased til like 70 and then eventually thrown off and definately die.
But yeah, at least in my case, I play fox as well so I simply wouldn't go falcon against a good sheik. I mean, if I was playing m2k's sheik it wouldn't matter, as the best i've done is take two stock off him, but against anyone close to my skill I wouldn't play falcon. It's just a very hard and not fun matchup.