A dynamically dexterous legged robot has the distinct property that the legs are continuously interacting with the environment. During walking and running, this interaction generates acoustic signals that carry considerable information about the surface being traversed, state of the robot legs and joint motors as well as the stability of the locomotion. Extracting a particular piece of information from this convolved acoustic signal however is an interesting and challenging area of research which we believe may have fundamental benefits for legged robotics research. For example, the identification of the surface that the robot travels on gives us the ability to dynamically adapt gait parameters hence improve dynamic stability. In the present paper, we investigate this particular sub-problem of surface identification using naturally occurring acoustic signals and present our results. We show that a spectral energy based feature set augmented by time derivatives and an average zero crossing rate carries enough information to accurately classify a number of commonly occurring indoor and outdoor surfaces using a popular higher dimensional vector quantizer classifier. Our experiments also suggest that VQ surface models may be velocity dependent. These initial results with a carefully collected but relatively limited dataset indicate a promising direction for our future research on improving outdoor mobility for dynamic legged robots.