So his recovery isn't nearly as good in 3.5 as it was in 3.0. He actually has very poor air mobility so he can't come in at diagonal angles. He either DIs up off a bair and then will likely try to jump over you and spin onto the stage, or goes low off of fair and has to spin to get close enough to the stage so he can either A. UpB and sweetspot or B. rise with an aerial onto the stage like fair or uair.
In the event that he goes high and you suspect he will recover high you can either bair him again because it beats out every move besides fair and bair, or fair him which does the same. It should be easy to react to unless he has a jump.
In the event he goes low he MUST get right along the wall of the stage to UpB because it does not go horizontal in the slightest. Always grab edge if he is coming from low and then use ledge invincibility to hit him with either a nair, bair, or reverse hitbox of fair if you can manage it. Getting used to using the invincibility is weird at first, but if you're playing Sheik it's something you should use for almost every MU anyways. Sometimes you can even get lazy and just drop and nair and he will either be KOd, gimped where UpB can't make it to the stage, or stage spiked. You want to use your aerial a little below the stage so he can't intercept with a rising aerial of his own. If you do it correctly he should be forced into your attack and won't survive.
There is a 3rd recovery scenario where he has a double jump and he's about even with the ledge where he can use homing attack to lock onto you, but it is incredibly risky because if it does not lock on to you or run into a wall he goes into special fall... You can make the homing attack not be able to detect you by using ledge invincibility. Because it's so risky I wouldn't expect the Sonic to try it too often.