Efficient exploration of space is a paramount motive for active colloids in practical applications. Yet, introducing activity may lead to surface-bound states, hindering efficient space exploration. Here, we show that the interplay between self-motility and fuel-dependent affinity for surfaces affects how efficiently catalytically-active Janus microswimmers explore both liquid-solid and liquid-fluid interfaces decorated with arrays of similarly-sized obstacles. In a regime of constant velocity vs. fuel concentration, we find that microswimmer-obstacle interactions strongly depend on fuel concentration, leading to a counter-intuitive decrease in space exploration efficiency with increased available fuel for all interfaces. Using experiments and theoretical predictions, we attribute this phenomenon to a largely overlooked change in the surface properties of the microswimmers' catalytic cap upon H2O2 exposure. Our findings have implications in the interpretation of experimental studies of catalytically active colloids, as well as in providing new handles to control their dynamics in complex environments.