When you play as Gaius you are dealt two loyalty cards at the start, and the same for Sharon in the sleeper phase. Because of this, there are not enough loyalty cards in the deck for everyone to get one in the sleeper agent phase. When using these characters do you add an extra (or if both are in play, two extra) you are not a cylon loyalty cards to the deck on set-up?

Yes.