Well, the blacksmith told you the keystone is in the Gold Saucer, so that's where you'll have to go. The Keystone is in Dio's Showroom, which is on the right-hand side of the Battle Square. Look at the Keystone, and Dio will come in. Accept his challange (You don't really have a choice) and suit up Cloud in a similar manner as you did Yuffie back in the Pagoda. Then fight as hard as you can. Don't worry about how well you do, because even if you wash out on the first round, you still get the Keystone. However, if you stick it out till the end, you'll get a Protect Vest and a Choco Feather.
Well, now here's one of the big spots where all those Love Points you've been scoring with Aeris and Tifa will pay off. Whoever has the most love points will be Cloud's date for the evening in a nice little scene. By the way, in the little play you participate in, if you talk to the wizard, ask about the dragon's weak point, and then kiss the princess, you'll get a happy ending. I've gotten to date both Tifa and Aeris. But did you know that Aeris and Tifa aren't the only ones you can date? You can also get Yuffie to ask you out. But here's the topper: although it's very hard to do, it is possible to get tough ol' Barret to soften up and admit his homosexual tendancies to Cloud!
Anyhow, during your date, you'll see Cait Sith carrying off the Keystone. When he runs away, watch where he goes, and follow him. You'll eventualy end up on the stairway in front of the Chocobo Races, and Cait Sith will toss the Keystone to the Turks. He then explains his true loyalties, and who he really is. He won't leave your party, though. He'll also give you the location of the Temple of the Acients, which is your next destination.