Update:

Got rid of the fat look completely, still have no clue on what to do for the scene.
KAT: If I may give some advice on your piece, try to go learn some basic perspective, this would help your piece alot(
http://www.olejarz.com/arted/perspective/ Some one-point perspective). The water looks very odd, the best game I can suggest for water examples is the Metal Slug series(They're also pretty good with skies, most images on google are jpegs, so my suggestion would to be to go get the rom and emulator, use google to find this, don't really think I can give them out on this site, so I won't). For the overall piece, you need more contrast and just better colors to fit the scene, so go google some stuff for reference and just look at other pixel art.
Kren: Looks great, could use some more dithering in places(Aswell as some good old Anti-Aliasing), add some more clouds, loving those and the ninja I think would look better looking more realistic, since everything else does. Oh also, the bamboo looks a bit odd, with it going from a fat bamboo to a small one.