I did watched this cartoon when I was a kid, although I didn't remember much of it, heck, I even completely forgot it existed, until I watched it recently in Tooncast, along with He-Man and She-Ra (wich I never watched as a kid and I consider it much better than He-Man IMO).
As I watched Brave Starr, I couldn't get off my head how cheesy it is much it reminded me of He-Man, with the same themes and situations, but much, much cheesier, almost like a parody (the Sherlock Holmes episode is so full of win, I even wished he was the protagonist).
Heck, it even featured one of those "lessons for kids" at the end of each episode!.