My first thought was someone that's just like Yuffie. Maybe not the actual Yuffie, but someone that mirrors her personality and is closer to Sephiroth's age (but still a few years younger). Think about it. Her personality may be the opposite of his, but because of this they'd complement each other, making up for what the other lacks. She'd cheer him up and bring out his playful side while he'd keep her grounded in the present (as opposed to her having her head in the clouds). It'd be a mix of creativity and logic. Rather than being book smart, (though not an idiot either), she would be clever and cunning enough to pleasantly surprise him. He'd tease her with big words that she doesn't understand to see her get flustered as she tries to figure them out. She would comfort him when he's upset, and he would hold her close when she's sad.
Sounds kinda odd, but i can picture it. One more thing: she'd know how to cook (since I cant picture Sephiroth doing it well) and she'd enjoy surprising him with dinner and birthday cakes.
I think this type of girl would complement him very well.