DitheringOnoez, you used the spray can! That's alright, some of us make that mistake at least once in our lives. Now, I picked a section of your work and dithered [semi]correctly, as you can see from
here. Sure, it seems difficult, but it isn't really, after you get the hang of it.
Here's an example of dithering between two colours- in which I cheated and used a monochrome bitmap, but hey, this is just for example.

There's just so much you can do with only two colours, huh? ;3
I'll be honest, it'll seem mundane. You will want to take frequent breaks. But it does make the piece look more uniform; The spraycan does dither, but it's like... speckle dither. You don't have complete control of each pixel, and that's what pixel art is all about.
Here, I removed the section I dithered [semi]correctly for visual sake. o:

Looks a bit better, doesn't it?
ColoursI can't really see the two top colours separately, from first glance. That's not what you want, ever. >D You want to use as few colours as possible, and because of that, each colour should at least seem like different colours right from first glance. Since I did this quickly, I'm afraid I still didn't do the job correctly, but the colours do look a bit better.
StarsAs Helm mentioned, 'stars are in constallations, not uniform patterened grids'. That doesn't mean that where you placed the stars are wrong, exactly, but the way they're placed does make it look like a grid. To mask that, you draw smaller, bigger stars around it. Again, quick job, but does make it look better.

Remember, stars have different sizes and intensities.
To get this done, I had perhaps... one colour more than you? I dunno,
Now compare the section I did to the whole
picture.
Jus' trying to help. Take from this what you want. I do suggest, even though you said you won't edit, to redo this piece in a smaller scale. ;3
Edit: Tried the colours again, added more stars to make me look less lazy.
