You can't really aa a horizontal line; it has no aliasing to anti

What you could do is use more dithering patterns than simple checkerboard, thus resulting in seemingly more colors and a smoother transition. That or you could just add a bunch more colors, but it's your call.
Also, you may want to consider cleaning up your art a bit. I know the focus is supposed to be the tree, but when my eyes drift into the sky, they get stuck on the moon and I start wondering why there's a strange, rough, irregular halo around it. If it's supposed to be a halo around the moon, make it circular at least. If it's not supposed to be a halo, then...remove it?
Another thing: if it's supposed to be evening, then the sky should probably be a bit darker. The night sky is pretty black where I'm from. If it's supposed to be nearer sunset than dusk, then the sky should be considerably more colorful; sunsets are rather vibrant.
Good luck with the piece; you've started quite nicely.