It's widely accepted that a robot's embodiment plays an important role during human-robot interaction (HRI). While many studies have explored the effect of robot appearance, relatively little is known about how the texture and stiffness of the surface material, or what may be referred to as 'robot-skin', influences how the robot is perceived. Gaining improved understanding in this area may have direct and actionable consequences on robot design, since at present nearly all commercially available service robots have similar exterior surfaces composed of smooth, stiff materials, usually plastic. This study is framed around systematically investigating the type of textures that may be better suited for these robots. First, experiments were undertaken to classify the textural characteristics of 27 distinct materials which could potentially be used as a robot-skin. A representative subset of these materials was then selected for a second experiment that explored how the stiffness and tactile properties of the material influenced its perceived suitability for use on a service robot. The research found that people strongly preferred surface textures that were soft, rather than stiff. The most suitable material stiffness was found to be context dependent; soft options were preferred in the blind test condition, but for cases where participants were presented with the 3D image of a service robot in an immersive virtual reality environment, medium stiffness materials were preferred. In the final part of the study, we identified a range of textural properties that seem to correlate with high and low suitability for use on service robots. It is hoped that these findings are useful to help inform the design of future HRI systems, and motivate further investigation into the social roles of robot-skin.