You have advertised it as a "story focused" game, so be sure to have a strong story with combats that are appropriate to the story (rather than random) and are climactic.
Toss in an occasional skill check and such to keep dice rolling even during story parts. Make it descriptive and just keep on the idea of "it's a story" -- that's how you've sold it and that's what they're expecting.
Sure, they may well love the combat aspect of it at which point you can gradually add more and more of that, but they're coming and expecting an interactive story, so that should be the start of it.
Something simple (since they are all new to it), but not necessarily straight forward (so that they feel they can all contribute in their own creative way)...
Go and rescue someone or recover some stolen thing of sentimental value (so it leads options open for direct confrontation or trying to sneak in, etc).
Maybe they have to defend a bridge or a town from zombies (but give lots of oppportunity for setup of some creative way to guard the town so that it isn't just straight to combat)
Maybe they have to protect the prince at the royal ball, but they don't know who the assassin could be so the king hired outsiders to protect his son (but this will take a lot of npc creativity on your part since it will boil down to lots of interaction and trying to give the right mix of regular conversation vs. dropping subtle clues via bluff checks)
the thing is, don't think you need to do something diferent because they are girls. your primary focus should be a) they are brand new RPGers and b) they are hooked by the idea of it being a shared story
(if you sold them the idea of come to kill lots of things then a war scenario or dungeon crawl would be a better thing to do)
there is no need to purposely make it a romance just because "they are all girls" -- only make it a romance if you know that all of them like romance stories.
And no combats for the sake of a combat, every combat should have a reason if they're trying to follow "the story"
And also try and be descriptive with PC power effects (you're not just damaging and pushing the opponent X squares with the thunderburst, but it's a surge of thunderous air that blows them back, etc ...)