It's totally readable as-is, but there's always room for improvement. I think the current sky colour is fine. Here's an abandoned game (http://forums.tigsource.com/index.php?topic=20939.0) that uses a similar colour palette with no outlines, you may be able to refer to it to resolve some of your concerns.
Edit: I just checked (http://www.color-blindness.com/coblis-color-blindness-simulator/) and your current colours are almost universally readable across different types of colour blindness, which surely counts for something!
I think there's good contrast between the dress and the background. You'll have to add the butts and mountains before you can really judge how well it works. Edit: I was watching the animation imagining that it was a game. When I look away from the character to scout the terrain or watch for enemies, her hair gives me a good grasp of her position. (So, does the fact that she's always centered.) The point is, I don't think the dress matters much for gameplay. It's just window dressing. If there are night scenes, then the dress will become the visual anchor.
When I'm picking color pallets I create rules for how to vary the colors. Backgrounds must have 16 bits less red and 16 bits more blue than foregrounds. Highlights are 20% more white for colors with a value over 50%, 10% for colors with a value under 50%. I know it sounds complicated. Just make up the rules as you go along. Write them down. Then whenever you question your color choices, refer to your notes, AKA: artistic direction.