There is a trick with Tifa. When you're imprisoned in the Shinra Building, Tifa asks if you think you can escape. You're given two options, and each time you talk to her, you can select one or the other. Just select either the positive or negative option a whole bunch (20-30 times should be good to be sure) depending on whether you do or don't want to date her.