Both by the same producer and explores the notion of bio engineered humans and other such possibilities. Although, Vexille is slightly more about the ethics of such research and experimentation. But both are equally good movies.
Both are fully CG animated scifi action movies, with very similar settings (like mech-suits and both main protagonists are members of a special units). And both stories are fairly straight forward and entertaining scifi-romp, without too much pointeless philosophy or thought.
Deunan Knute and Vexille are both young, pretty and athletic type ladies. They both take place in futuristic settings and the stories in both those animes involve androids and advanced armor used in combat. The director of Vexille, Fumihiko Sori, and the writer of Vexille, Haruka Handa, both worked on Appleseed.
Also, they both have great action sequences (even though I think Appleseed had better ones), great looking CG and music artists like Paul Oakenfield, Boom Boom Satellites and Basement Jaxx both were part of the soundtracks for both animes.
Both movies have the marvelous mind of the sci-fi guru Shirow Masamune behind it, so you must expect a good storyline (Appleseed's not a masterpiece as GITS, but it's interesting anyway).
The animation is awesome too, and the action scenes will keep your eyes on the screen until the very end. If you're a sci-fi fan, both movies are a good shot.
The underlying themes are similar. A global system that totally controls behavior of individuals in a futuristic town depicted in a quite elaborate sci-fi fashion. An attempt to dissect the eternal dilemma of happiness vs free will. A happiness that is nurtured/enforced by the system in order to prevent the basic barbaric instincts of human race from instigating suicidal wars.
Pacing-wise, the two movies start off with a cool action sequence involving the heroine and while Harmony becomes a somewhat philosophical contemplation woven around an investigation by a Helix inspector (the heroine) Appleseed keeps being more action-packed.
police forces on the street, futuristic cities and in some cases half cyborg villians run on the loose, Both have same job they´re cut out for and have a man&female main cast with the right TO BEAR ARMS!! phew
Both movies are full of action, cyberpunk, sci-fi weapons and gadgets, with a few high-quality hand-to-hand combat scenes, both have a female protagonist and what left of civilization is controlled by an artificial intelligence system that decides what is best for people, but the methods are questionable and those questions are raised by the female protagonist in her dangerous journey.
Appleseed and The Spirits Within are sci-fi movies done exclusively with computer generated technology, which lends them the same overall feeling, 3D animation dominating the viewing experience almost completely. The plot is similar, in both cases humanity is at the brink of extinction and it is up to scientists to come up with solutions.
They both rely heavily on CG but the work is exquisite. The stories are also in similar settings, the desolate future. If you liked the animation style and storyline of Appleseed then you may want to try out Wonderful Days.