I first heard Michael on that first Dreams album. Then on a Horace Silver record. Both were with Randy onboard. The there was his solo on James Taylor's "Don't Let Me Be Lonely Tonight". Then with The Brecker Brothers albums - "Sneaking Up Behind You" was a pop hit, and "Some Skunk Funk" was/is a "cult classic". So he was a very well-known quantity before Steps.
Both Michael and Randy did a good amount of session dates, and Michael stood out everywhere he showed up. But he never really attempted to create a "straight-ahead" profile. Until all that had died down Check him out on Cameo's "Candy", that has become an iconic moment for players of a certain ilk.
Along the way, he'd do the oddball "straight ahead session, like with Joanne Brackeen or Hal Galper, but those were always on low-profile labels. So when he showed up on 80/81, it was a bit of a WTF? moment for a lot of people. I remember Bob Belden talking about it and smirking that "Ok, everybody thinks that Michael Brecker can play now because he's on a side with Dewey".
That was snide, but not inaccurate. He was playing a lot of flash, but not a lot of meat, imo. To his credit, apparently felt the same way, and spend the rest of his life being humble and working hard to keep digging deeper. Me, I didn't really care, but I came to respect the hell out of him, and do understand the high esteem in which he came to be held.