Contemporary work environments require humans to process audiovisual information displays whilst moving around the world. The attentional demands associated with using devices such as in-ear headphones and head-mounted displays may be significantly influenced by varying locomotor demands, yet this relationship remains poorly understood. This study investigates the interplay of information presentation modality, movement state, and cognitive task difficulty. In a virtual reality laboratory, 22 participants performed a cued task-switch paradigm with two difficulty levels while standing, walking, or walking with perturbations on a treadmill. We used a questionnaire, behavioral and mobile EEG data to investigate cognitive-motor interference. We find that locomotion interfered with cognitive task performance, and that the presentation modality of task-switch notification modified the nature of this interference. While auditory cue presentation resulted in faster responses under low cognitive load conditions, visual information presentation was less impaired by higher cognitive and locomotor demands. A detailed analysis of the EEG response to cues addressed these differences in terms of multi-modal attentional mechanisms. Hence, wearable information presentation should be tailored to the specific needs, particularly for cognitively demanding information in mobile work settings.