The sprites look great. I would make the background using only the 2 lighter colors of the palette, otherwise the sprites would become too hard to see. If you look at most GB games, sprites usually use the darker colors while the background is light and low in detail. Some games try to use a white outline on sprites so they stand out, but to me that just makes harder to see exactly what they are supposed to be. In a game with only 4 colors, readability is the no. 1 priority