I think the thing to remember with Malak is he was a "Vader-like" character, thus he wasn't so much a evil mastermind like a Palpatine would be. He was brute force, such as Vader was. Vader wasn't a tactical genius. In fact, a few of his tactical decisions backfired. Much is the same with Malak. He's not a strategic genius, nor is there any indication he's overly intelligent (hence why Revan was his master due to Revan's brilliance in combat strategy). His role was to be the big, bad, tough guy you had to defeat with might, not with intelligence or cunning.
I think people are underating Malak as a villain purely because they try to compare him to guys like Palpatine or Thrawn, when in fact Malak was more like a Darth Maul or Darth Vader type villain. And in that respect, I thought he was a decent villain.
note: I STILL think Darth Vader is the ultimate "tough guy" villain, and no one, not Malak or Maul, comes close to him in that regard