Usually you want your sprites to be more saturated than the background elements that aren't as important. The problem with using grey as sprite colors is that when you desaturate a color you move it towards grey. So your sprites are going to seem more neutral space when you use grey colors on them.
You could always try something a little different and rather than working on trying to find a contrast point between shades of grey, you could adjust the bricks that are gray to something that works better with your sprites.
For example why can't your bricks be a dull purple or red color?
I did an edit toying with the colors. Brought the saturation on your sprite greys up and changed the environment colors to something that let them stand out more I think.
A lot of old games worked very hard to avoid grey colors on their sprites. This is why you see so many blue/green/red sprites. Those colors just pop out and are easy to see.
Not sure if this is anything you can use or if it helps you find a happy place but I will post it.