For the most part, the tiles have a nice and clean feel to them. Some of the wall tiles seem inconsistently lit, though, with the light source coming from various directions without any local light sources to explain the change.
I second the part about the outlines making the sprites look flat. The bright outline dominates the sprite, making the volumes of the shapes within less apparent. I think a better approach is to get rid of the outline and use the brightest shade to increase contrast. Whether you should brighten the darkest shade as well depends on the dominant background color. Most importantly, you'll have more room for details. One pixel is a lot at that size.
As shown here, bright and dark together stands out against both the dark tiles and the brighter ones. The brightest version looks a bit more flat, but stands out more against the darker tiles. I also found the feet hard to read, so I made them larger.
I also got rid of the lighter shading on the floor tiles in order to further emphasize the sprites. By keeping the floor as simple as possible, it's easier to spot the sprites. If you feel the floor looks boring, I think it would be better to add some more wall tiles or similar variation to break up the monotony that way. Otherwise, I would use the darkest shade for variation instead. I also tried to get rid of single-pixel noise, leaving just enough pixels to give the impression of rivets.
What do the smaller sprites represent? The leftmost one is a little dark in my edit, so I also added one which is brighter along the edges to show its full size better. I think a better alternative is the rightmost version using the two brightest shades.
For the wall tiles, I made the highlights along the edges thinner to match the style of the other tiles.
