Alright, let'see, checking in with some art direction advice here.
Here's the thing: So far you've got a sketch for a couple assets. You don't have a complete plan here. If you're preparing the art direction, you have to figure out what all the assets are going to look like. This doesn't mean literally drawing everything, just have a plan for how to extrapolate the style of a few examples across your range of assets. And you're still grappling with the tree, so you've got a ways to go.
So, first, you gotta know what your full scope is: Make a full list of every unity and all terrain types. This plan can change of course, but make a good guess and call it your first-draft plan so you can figure out how the details pan out to fit the whole.
What you seem to be doing here is making some art examples to base the rest of the game on. This is good, but you're not done - you gotta animate at least one walkcycle for that footman and, I think, do a full turnaround with whatever number of directions you want the sprite to face. This'll let you appreciate the amount of work it's going to take to do that art for one unit, and then for all the rest of the units. Then you can decide if this is what you really want to do -- and I bring this up because it looks to me like you may be walking into a lot more work than you expect; it may be valuable to go much simpler in style so you can finish the thing.
As for the tree/terrain, you're going to need to do a mockup of what you want it to look like. To give an example of this, I planned a terrain set out a while ago by first doing a small example set of assets and fitting them together in Photoshop. It looked like this:
[attachment=35267:tileset_test.jpg]
You can see that I'm pretty happy with the beaches, but I'm doing a lot of experimenting with rendering trees and so on. Using this art as a base, I extrapolated out various terrain types, two different kinds of forest, mountains, rivers, etc. (It was, as ever, more work than expected.)
As for the particulars of your tree, I highly recommend reading this pixel art tutorial at Android Arts. It's just really good and addresses issues with colour use, rendering, noise, composition etc. highly applicable to the visual design issues you are facing. Particularly good is the part at the end where he takes a problematic scene and re-renders it according to the rules he's discussed, then shows examples of other pixel artists taking on the same task in different ways; I can't recommend it enough.
Overall, I think it's likely you'll want to pull back the complexity and detail a bit to make the project more manageable, seeing as you're also doing the coding. Best of luck!
PS. Is your username a Total Annihilation reference? Nice.