I'm guessing it would be alright to bump this back up now that I have an update. I've been a bit busy lately and hadn't been able to work on this, I started up again and have a new version to show:
The team for the game I'm working on has finally decided on a size so I ended up making the sprite a bit smaller, the sprites will be based on a tile size of 18x18 rather then the normal 16x16. At the moment she's 38 px high which should be alright with the 18 px tiles, the very bottom pixels of her boots will likely be 1 px into the ground tiles so her hair will only clip with the tile above her by 1 px, which is hardly noticeable.
I changed the palette a bit and made it a simple 8 color palette and I removed some more black based on what Helm had shown. The background is just something simple I put together to see how it might look.
I'd like to try starting a walk cycle at some point, but I'm not sure if this is a good starting point or if I should try for something where she's facing the right a bit more so if anyone can give me some advice on that I'd greatly appreciate it.
[Edit] Did a bit more work on it:
The tiles are a WIP as well so if anyone feels like giving any C&C on those I'd appreciate it.
The main thing I'm worried about now is the sprite though, I'll likely make a separate topic those tiles and the rest that I'm working on later.
[Edit 2] Here's the newest version: