Don't live or spend much time in SH since I'm usually there for work (ie. lots of hotel meals, short stays), though Ali Baba Xinjiang restaurant (930 Renmin Lu) was quite nice, though I have not been to any other Xinjiang restaurants in SH.
Snack street or 小吃街 is quite nice...