Data frequently dwells outside established UFP territory without starving. For all we know, his batteries could last for years, and it still wouldn't contradict the concept of him constantly recharging from an outside source.
When Data listened to several overlapping musical pieces, none of them was particularly quiet; the ability to hear them would not equate to the ability to hear footsteps from afar, then.
(As an aside, sound is sound: Data wouldn't have been able to discern the different pieces unless he already knew all but one of them, and by that means could tell which sound belonged to which piece. Analyzing a complex but unknown
soundscape would be significantly more demanding.)