Why the big difference in sketch size when using byte and integers?

You're mixing program memory and SRAM. A byte takes up half the space as an int in SRAM, but handling of the two in terms of number of instructions may vary.