The ones in the centre are mostly like the ones in Madrid, on one floor of a building. Hostal Larios is pretty good. It's on the newly pedestrianised C/Larios, shown here
http://www.malagaturismo.com/varios/esp/webcam.htm You can easily check out a place by calling and asking to see the room first. It's normal, there's no problem.
Hostal Capri is to the east of the centre (walking distance) along Paseo de Reding, and is a whole house. Nice rooms, with bath. It's the only hostal I know of near the beach.