Yup, got them both on my first play through. Came across Yuffie in the woods near Fort Condor. I had a magazine which told you the correct responses so I didn't have to catch her loads of times.

I thought Vincent was pretty easy to get. He always stops me on the way out and asks to join. You just need to chat to him when you first get to the basement. His chamber isn't overly hard to find.

EDIT:

Quote Originally Posted by Bubba View Post
Came across Yuffie in the woods near Fort Condor.
Possible poor choice of words.