Just to clear this up, cellshading isn't directly a graphic style, but rather a sytyle of. yep, shading, which is often used in anime. That doesn't mean it has to be "comic-y", just look at hellsing - thats a special type of cellshading and it doesn't look too much like windwaker, does it?
That being said, I think you're on the right way. Just add some structure to the ground and find a way to do outlines that don't distract too much and this might turn out awesome. Btw, someone on RRR is doing a similar thing.