Spock wears Commander braid from the first regular episode onwards, but is referred to as Lieutenant Commander in two first-season episodes where certain formality is observed. One could say he was "promoted stepwise" at the beginning of the season, "frocked" so that he got the rank braid and prestige, but his paperwork was delayed so that Starfleet could avoid paying him in full.
Yes, Scotty and McCoy are LtCmdrs. Some Security redshirts wear full Commander braid, although Giotto in "Devil in the Dark" was referred to as a Lieutenant Commander, perhaps being "frocked" like Spock earlier on. The archives head honcho and computer wizard Ben Finney from "Court Martial" was a LtCmdr, too.
(However, goldshirt Kelowitz was a mere Lieutenant, despite my claims to the contrary above. It's an annoying error in the Encyclopedia... The LtCmdr in "Arena" is actually the blueshirt Tactical Specialist Lang, another possible case of "frocking" in the sense that he gets called Lieutenant once or twice.)
Basically every second redshirt we see is a Lieutenant - the rest are either Ensigns or crewmen. Many appear older than Sulu or Uhura. Plenty of background personnel in gold or blue shirt wear the Lieutenant braid as well, and have a few years on the bridge heroes.
Timo Saloniemi