Multi-sensory feedback can potentially improve user experience and performance in virtual environments. As it is complicated to study the effect of multi-sensory feedback as a single factor, we created a design space with these diverse cues, categorizing them into an appropriate granularity based on their origin and use cases. To examine the effects of tactile cues during non-fatiguing walking in immersive virtual environments, we selected certain tactile cues from the design space, movement wind, directional wind and footstep vibration, and another cue, footstep sounds, and investigated their influence and interaction with each other in more detail. We developed a virtual reality system with non-fatiguing walking interaction and low-latency, multi-sensory feedback, and then used it to conduct two successive experiments measuring user experience and performance through a triangle-completion task. We noticed some effects due to the addition of footstep vibration on task performance, and saw significant improvement due to the added tactile cues in reported user experience.