I'm not the hugest fan of introducing puzzles like this into games but I think the best way to do this is to solve them out of character and then, if necessary, roleplay the solution in character. So long as everyone knows that you're going to do this (announcing it beforehand might be a good tactic), it eliminates or at least reduces many of the issues at play here: the player playing the barbarian can "suggest" the solution to the wizard without nerfing the barbarian (by refusing to allow him to partipate beyond a certain low level) or overpowering the wizard (by allowing him to roll a lot against his INT or knowledge skills for hints), by allowing this bit of out of character-ness you don't penalize players for not choosing a character which is a milieu-specific version of them, and so on.
The biggest drawback to this to me is that bit of OOC stuff, though. I'm already not the biggest fans of puzzles in games, to be honest: as a player, I tend to attempt in-character creative solutions to issues as opposed to attempting to ferret out the "right" one, and as a GM, well, too often these things come down to "have you read this puzzle somewhere before?" rather than "here is an INTERESTING conundrum to test your wits!!!". I understand that a lot of people who like RPGs also like these kinds of games (and admittedly I do too, although my time of enjoyment is primarily when I am on an airplane, not hanging out with my friends) but I'd personally caution against using them too often.
What I do instead is that I come up with a big problem that the characters have to figure out how to resolve on their own. Let's say they need a certain amulet but that amulet is locked up deep in a castle. Some parties might choose to storm the place, others might try to bluff their way past the guards, still others might try to infiltrate it sneakily. If I'm concerned that the players will get locked into one particular course of action (if you're playing DnD, isn't violence always the first, second, and third options?), I might spend a bit of extra time on the situation detailing the kinds of things that might happen if they go that route (in this example, maybe there's a local village whose leader is being held hostage; a frontal assault that alerts the guards will cause this man to be killed... or perhaps the bad guys are just too powerful, granted that IME DnD players tend to be particularly unable to comprehend what constitutes "an unfair fight", so tread carefully). Otherwise I design the major players in the situation and do what I can do to not devise a single railroaded option.
That method requires a great deal of improvisation, I realize - there's only so much prep you can do for "I will allow the characters to do whatever they want here" - but to each his own.
Another tack you can take is to greatly immerse whatever "puzzles" your giant friend is giving deeply in the game world. "If the Duke of Castille is poisoned to death, who is next in line for his throne?" That question may require a couple of successful rolls against local politics and the like to even grok the nature of the puzzle itself. That, at least, is a way to encourage players to keep spending points on non-combat skills.
Still another thing you can do, which, depending on the game system might require a small bit of re-envisioning, is to not take INT scores or their equivalent as the be-all and end-all of intelligence. A barbarian with a 7 INT might not actually be stupid, but instead ignorant and, by and large, completely uninterested in anything that doesn't involve bashing something in the head. Likewise, you can explain away a high-INT character being played by a less than quick-witted player by saying that they're logical and methodical and so might just not be all that great at quickly solving puzzles like this. I think this method still has the issue of encouraging people to RP copies of themselves but if the campaign is otherwise going well and you just need a handy explanation for why the barbarian keeps coming up with the answers, this can work.