Currently, GameServer has a set of GameInstances, and GameInstance has a set of players. This requires me to iterate through every game and player to find the correct game, and I don't think this is the best way to do it, because it will have to be run hundreds of times per second.
You're right! And while I will answer your specific question, what you should do is read about datastructures. It's essential that every working programmer have at least a basic understanding of the most common datastructures, and their performance characteristics.
Based on your description of your problem, you need to maintain a mapping, probably using a hashtable, between a key which identifies each game, and the object which describes it.