Yup. Children's Palace! I remember the catchy TV jingle (Children's Palace - That's Where It's At!):
It felt more like a toy warehouse inside compared to Toys R Us. And the video games were right in the front and you could flip through boxes instead of the card system. I recall seeing Superman on the NES and River Raid 2 for the 2600 there. I also saw a Wonder Boy in Monster World for the Genesis, but I can't remember if I bought it there. I might have when they had a going out of business sale. I also recall some special sets, such as a GI Joe 2 vehicle set I bought on clearance that including two extra, random figures. You didn't see these at regular stores.
Also, I once found a vintage Human Torch Mego figure on the shelf in the clearance section, well after it's run. Where else could you find a toy that was discontinued 5-10 years earlier?