I noticed there didn't seem to be a thread for this yet, so I figured I might as well start one up, in a similar vein to the MaW1 thread I made a couple months ago, except spoiler tagging the whole thread this time, as the patch exists, so it isn't so much to convince people to try to play through it, as it is to discuss and share opinions. I'll start off with my own thoughts on each of the girls, both story-wise, and battle-wise.
My Playthrough order: Mena->Lucy->Kitty->Aoi->Sheryl
My Girls ranking: Aoi=Lucy>Sheryl=Mena>Kitty
Mena: I picked her route first because I suspected I'd like her least of all the girls, however, I was pleasantly surprised. Maybe I've played enough eroge at this point that I'm over my initial squeamishness of bedding your little sister (all technicalities aside), or maybe Mena was just a sister character that was finally written right. Unlike, say Akiha, she wasn't completed fixated on her older brother, and her affection snuck up on her and took her by surprise. The scenes when she was finally self-conscious in the changing room, and when she walked in on Cliff were done just right, in my opinion. Her plot connection was rather weak, aside from Lucy's her story was the least related to any of the core plot out of any of the girls, so that was a downside. Her H scenes did not disappoint though, as they included not only oral, but the added bonus of Kitty threesome. Overall she also suffers a little due to lack of real influence in the other girls' routes.
Battle-wise, however, Mena is an indispensable addition to your line-up, as RotPumpkin is the singularly most useful tech, ever, and several of the other tamed monsters over quite a nice variety of abilities, giving her unparalleled flexibility. Her physical stats are a bit sub-par, though, in my opinion, and the double-edge sword of needed to tame the monsters (which can get very tedious) may make her less attractive than some other options. As far as equipment, I typically gave her a "shield" item, the Good Sandals (if Sheryl wasn't using them), and one of the elemental resists as filler.
Lucy: If only Lucy had a more plot-central role, she would easily have been top girl, in my opinion. Her personality is fun, laid back, and enjoyable, and comes through in so many ways (like her habit of using pet-names for people, when she spies on you in Aoi's route, the way she teases the other chosen girls in the Big Bath scenes, etc.). She also has the extremely sympathetic side to her as well, though, as evidenced in the Baby Job, and her sad past. Her voice acting was absolutely top-notch; I loved her accent, and the expression in her voice. Her H scenes were quite disappointing, though, to be perfectly honest, compared to some of the other girls they were quite few and quite vanilla. While her own route was rather weak, she at least had decent staying presence in the other routes: most notably that she had good placement as a older sister figure to Kitty, and that she noticed Cliff and Sheryl departing for Old Castle, in the final route and arrives with the rest of the crew to save the day.
Battle-wise, Lucy is an absolute physical powerhouse. "Trigger-happy" is an incredibly useful skill for hitting multiple enemies, and unlike Cliff, who also has multiple hit attacks, she can actually use it frequently without worrying about being able to save Force for Double Attacks (as much). Additionally though, she has the cheapest Heal Party tech of the girls (aside from Mena's RotPumpkin). The only downside is that her combo affinity is on the opposite side of Cliff's, meaning that if the third girl takes time out to heal (which she will), you won't be able to combo with him. Typical equipment included Knuckles (as "hustle" makes her already high attack even more brutal), an item that gives "quick" status, and an elemental resistance filler.
Kitty: Absolutely, abysmal. When I saw that there was another succubus in this game, I had very high hopes. They were completely smashed the first time Kitty opened her mouth. Her VA was terrible. I couldn't stand the tone, she was like a whiny child. Though, to be fair, she _was_ a whiny child. Which was another strike against her. For me, loli has to be done well (and it can, Ren was certainly an example of one). Kitty was not done well, as her character art just did not appeal to me. Not even her (minor) plot connection as a Cyphon, nor her (surprisingly) decent H scenes could save her. Maybe I'm unfairly judging her against Kahlua, but she could have been so much better, in my opinion.
Battle-wise Kitty was pitiful. No redeeming techs, terrible join time, and stats (barring attack) that need badly to catch up to the other girls'. Bench her immediately, and save yourself the hassle of raising her.
Aoi: Surprisingly pleasant. While she has a very reserved and almost prudish personality, it works for her, and can actually be kind of charming at times. Her plot connection was absolutely top-notch, and her end game was my personal favorite (I'm a bit of a sucker for the noble sacrifice aspect that Sheryl got to deliver). By the time one gets around to her route, the change of pace from that of the first three is _very_ welcome. Good H material here as well, both in quantity and quality.
Battle-wise Aoi is quite decent. She'll be your main healer until Mena tames the right monsters to take over, and can still do a decent job even after. I usually outfit her with either the Rosary or the Talisman (exorcist, duh, she's ought to be an undead-killing machine), an item with "quick" and an elemental resistance filler.
Sheryl: For the locked-in final route heroine, I was a little disappointed. I'm not sure why, but I had a harder time getting attached to her compared to the other girls (save Kitty). It might be her amnesia or the fact that she was forced, removing the element of freedom in picking the heroine? She did do excellent comic relief, though, had completely vital plot significance, and played an awesome part in Aoi's end game. Her H was sub-par, competing with Lucy's for worst place.
Battle-wise, Sheryl suffers from some of the same problems Kitty does, with respect to join time, and playing stat catch up. She can be extremely fragile, but she has some pretty vital techs in "Wake Up", "Keep Going", and "I'm Mad". I think her DA animation is the shortest, so that's a point in her favor there too. Typical equips are Good Sandals, a "shield" item, and an elemental resistance filler.
For completeness, I've included the following Battle info on Cliff.
Battle-wise he is absolutely essential due to his need to participate in Double Attacks. You probably won't want to use his Force for anything else, except the occasional "Breath Control" and "Whirlwind". Typical equips are Headband (for "guts"), an item with "quick", and an elemental resistance filler.
As a reference, I usually build their stats in the following progression
Talk about Men at Work! 2 related topics here.