Is the base sfx "good" (ie does it sound like what you want)?
Placing the sfx in 3d space can make a difference.
If the sfx is a mono sound and is not played in 3d, it won't feel stereo because it isn't.
Calinou's suggestion of a random set of variants will make a big difference. Not even foot falls sound the same from left to right.