I suspect you could beat Tyrant and Kozilek with a level 55-60 Gideon 1 with only commons and uncommons. As long as you’ve got a couple of first strike / double strike creatures (the best two are uncommon, Consul’s Lieutenant and Iroas’s Champion, though the rare Knight of the White Orchid is fine as well), a few removal spells (Smite the Monstrous is the best and that’s common) and a couple of ways to stay alive or regain life (I use the uncommon Knightly Valor and War Oracle and the common Enshrouding Mist; you could also use Blood-Cursed Knight or even Enlightened Ascetic, because you’ll be pumping your creatures with Gideon’s middle/top ability and Knightly Valor). None of the rares in my Kozilek-beating Gideon deck are “must have” at all (I only used 3: Suppression Bonds, Sword of the Animist and Knight of the White Orchid).