Gates was CEO from the beginning of Microsoft until he became Chief Software Architect prior to his retirement. Ballmer became CEO after Gates. There was never a gap between founding and CSA where someone else was CEO of MS.
I though John Shirley was the CEO for most of the 80's:)