I just picked up Exodus and noticed on p. 6 that it says there is an extra card in the loyalty deck now. If you're still only dealing out 1 loyalty card at the start of the game and another in the sleeper phase to each player, doesn't this mean there would always be 1 card left over in the loyalty deck at the end of the game? Is this right?

Yes. A new "feature" the game. There is always an outstanding card... and if someone is executed post-sleeper, they could still draw a critical card (not only a "you are a Cylon", but also the final five and personal goal cards).