Sondheim's deserving of all the praise he will get from people better able to give it than me. I like musicals, but it is the case that not many of them actually get close to living up to the promise of what they could be, and many of those are by Sondheim. Not enough composers (the ones that get produced and therefore I know about) aspire to do what Sondheim aspired to do.
More an Assassins and Sweeney Todd fan than Company, though that's more about me not the relative quality.
Also mostly don't find his music that enjoyable as standalones, the songs are part of a bigger whole. Never really have an answer to, "What are you favorite Sondheim songs?" They're telling stories, not tunes to be belted out. Other people differ on this, of course.
Slightly strange being old enough to be just aware of a time when he hadn't quite achieved icon status, and he had his share of not very successful shows. Age is funny.