This answer is in two parts. “Option” 1 is explicitly not what you are looking for – but I suspect it is what your players are looking for, and I offer it as insight into what I suspect they are thinking, as well as introduction to where I’m going with option 2.
“Option” 1: Refluff freely.
A trivial option is to keep character-building options available to your players. Let them use a goliath—’s stats. Let them have powerful build, take Mountain Rage, whatever. Orcs are usually big; he’s playing an extra-big orc.
Or let him use the bard’s stats. Thieves and rogues are often known as silver-tongued devils; having a party face is not a bad thing, nor is it inappropriate for a thieves’ guild. A bit of magic fits too; there’s a reason the assassin class gets some.
And, I suspect, this is what your players have in mind when you pitch these kinds of games. They seem to interpret them as a pitch for a particular concept or campaign idea, not literally a restriction on their character-creation options. That’s why they’re “thinking outside the box” – in their minds, they’re not. Their suggestions and reactions are quite reasonable and realistic, after all; you don’t even really have to refluff a bard in the first place to let him be a thief. And barbarian tribes are definitely not literally populated only by people with levels in the barbarian class. So I suspect such a campaign would work quite well for them, and they’d find it quite enjoyable.
But this doesn’t seem to match your desire to “let their role-playing and problem solving set their characters apart.”
For that you need...
Option 2: A different system.
You have a group who, as described, really enjoy the character-building of the game. One of the most exciting aspects of the system for many people, including, apparently, your players, is crafting your own character from all the tools and resources available. Not getting to do that is, to many, tantamount to not getting to play at all.
3.5 is also system that posits some roll, or sequence of rolls, as a solution to every problem, and the “player skill” aspect of the game comes from crafting a character. It is a system that indicates that success is about the character’s abilities, not the player’s. In effect, “their role-playing and problem solving” is not what the system itself is telling them “sets their characters apart.”
So when you start a game of 3.5, you are implying a number of assumptions to many people, including your players, that crafting their character is a major part of “playing,” and they are likely to take any pitch that is first predicated on that system as more of a conceptual idea, not a literal limitation on options – because that would be taking away the actual play, and why would you do that? You are basically asking “how do I tell my friends to stop having their fun and instead make my fun happen?” and that’s simply never going to happen.
You can try to pitch the game harder, you can try to get buy-in, you can try refusing to run anything else, or shelving a campaign idea until people stipulate to your rules – but my guess is you’re either going to die holding your breath, or, at best, you’re going to get a game that people are not terribly interested in, and that won’t be fun for you or them.
So maybe try a system that doesn’t have these sorts of expectations ingrained. A more narrative system seems best – it’s something of a cliche on this site, but Fate seems like an excellent choice for this. Because in 3.5, playing a goliath means you get to try different things, do different things mechanically, than being an orc. The races have different options. If the things the goliath can do interest you, but those that an orc can don’t, then you’re going to want to play a goliath. Refluffing, above, is one solution. But if you, as DM, don’t want those to be the things that set the characters apart, you need a different one. Fate, and other narrative systems, don’t have nearly the same problem – the player can describe their orc as they want.