Vincent is hanging out in the Nibelhiem mansion and Yuffie is hanging out by forests on the world map. The best place and time to get Yuffie imo is before going to Junon.

Both of them are going to take a little work to get them, but they're both worth it in the end. Yuffie while highly obnoxious is a excellent fighter and some some really good and handy limit breaks.

I would forget about Aeris and have Yuffie instead as her healing limit break is just as great if not better.