Er, that's a lot of questions. I haven't played yet, there isn't an english patch yet (for what it's worth, I haven't gotten the patches for the previous two games to work), I've never been any sort of good at Touhou so I'm not the one to ask, Aya and Cirno have both been playable in a few games including the fighting games. Actually, Cirno being strong enough to be playable main character in a standard game is a plot point.
Regarding Okina Matara, her Touhou wiki page indicates she is actually a Youkai Sage and it's implied that she knows Yukari. Their powers are fairly similar too.