Okay, this is what I did when I started my gaming group recently. I advertised a bunch of ideas I had, different genres and game systems I could run,and people who were into them responded.
Then we met and discussed what kind of game everyone wanted to play. Instead of asking them to choose a favorite, I asked them to veto any that they would have no fun in.
For your example, you have a player who is combat heavy and a player who is puzzle heavy. Come up with three or four ideas for a campaign. Try not to write a story, write an environment instead. Because to avoid interacting with your environment they have to completely flee the country / continent / world, while to avoid your story they'd just have to sit around doing nothing.
We can assume Meat Player is going to veto anything heavily cerebral or social. And Brain Player is going to veto anything that's complete combat. I'd suggest a dungeon crawl, as they are densely packed and have plenty of opportunties for combat, puzzles, social interaction, etc.
If you create a challenge that is the hinge upon which the adventure turns, what will you do if they don't overcome the challenge? Instead, think about what happens if your challenge is missed, ignored, completed, or uncompleted. It's your job to make sure the game can still go on in any of those four outcomes.
Fight Example: The players should be able to find the objective of the adventure even if they sneak past the fight. They could screw up if they lose, but that's their fault.
Puzzle Example: The puzzle should not be the lock that holds the Big Door closed. Because if they can't figure out the puzzle then they're stopped cold. Instead, solving the puzzle opens up a side route that's easier or more profitable, or makes a section of the dungeon easier.
"Railroading" is the extreme end of the DM making choices for players. The "Sandbox" is the other extreme - the DM gives little to no direction. Both are probably not good for most groups. You need something in the middle.
This means you can't plan ahead in your "story". Instead of a linear story you need events and possible outcomes.
Bad: The PCs kill the evil noble, and find his secret room, and decipher his coded journals which reveals where he's hidden the princess.
Better: IF the PCs stop the noble's plan, then ...
IF the PCs join forces with the noble, then ...
IF the PCs don't join or stop the noble, then ...
You write a little blurb about what might happen. As you get to be a better DM, you can do more of this on the fly, like you can do to create encounters, treasure, dungeon layouts, NPC personalities, etc.
The main thing is to not make choices for the players. You control the whole world and they control just one character each. You have enough on your plate. Let them play with their toys.
That said, the DM can't let the players run him ragged. You're the referee. You're the one whose common sense is deferred to. You're the one who decides how the world reacts to the PCs' actions.
Example: Meat PC puts on his equipment and runs out into the street to kill stuff. You describe the street: it's morning, there are some people out on their way to the market, a pair of rat-catchers strolling along with that night's catch, and a couple drunks staggering home. You roll a chance that there's a City Watch patrol, and tell him if there is or isn't.
Meat PC runs up and whacks at the rat catchers. They scream, drop their rats, and run off. If a Watch patrol is present, they will try to stop the Meat PC from killing people. If there isn't a patrol, roll a chance every round that one comes. Certainly the rat-catchers will look for one and bring it back with them.
Meat PC, stereotypically, will probably fight with the City Watch. And since he's a low level dude, he'll probably lose. Maybe he runs away, in which case he's a wanted man. The punishment for assault varies depending on the wound, but he could get away with a stuff fine.
But if Meat PC manages to kill the City Watch, say because he's high level or super lucky or uses excellent tactics, it's not a big deal. More will come eventually. And if he's wanted for the murder of the constables he's not going to be doing much besides fighting with the law. And eventually the army. And high level bounty hunters if he really persists.
The problem with this sort of escalation is usually that the DM either gave the PC too much power to start with (a starting PC or a normal human should be killable by a maximum-damage non-critical weapon hit) or on the other side of things giving the authorities too much power (again, a town guard should be no more powerful than a newbie adventurer, perhaps a Level 2 instead of a Level 1 if they're veterans, ex-military, or officers; Level 3 for elites and upper officers and a local 9th level Lord's bodyguards, though a King's private bodyguards will be high level).
If the PC is too powerful in relation to a common man, he will be drunk with power from the start and walk all over everyone. Which is a weird situation for someone who is supposedly desperate enough to enter a dungeon because he's otherwise completely unemployable.
If the PC is too weak in relation to the authorities, the player will feel shackled and overborne, and he won't have much fun. I've played in games like this and they've turned into "Player vs DM" which is really not how things should be. You're not the adversary of the players.
A good middle ground is to have the PCs be tougher than a normal peasant, about as tough as a street thug or town guard. After a few levels they should be the toughest dudes in town except for exceptional folks: other adventurers, knights and barons and such, important temple clergy, individual wizards, etc. And after a year of real-time play they should be among the more powerful people of the country, except of course they might not have the same wealth or influence as a duke or king.
This guy is going to be interested in puzzles. But a puzzle doesn't have to be a bunch of blocks you slide around. It could be figuring out how to get to an out-of-reach treasure, or what to trade with the natives, or which mushrooms are poisonous and which give magical powers. Look at the environment as a puzzle.
That doesn't help you much in actually creating these puzzles. I guess my answer would be to not make things easy for the PCs. In making things harder or more complex you create puzzles for free.
Example: You have a treasure in a room. Not very exciting. Instead, put the treasure at the bottom of a well, guarded by a Water Weird that attacks anyone who comes near. It tries to drag them in and drown them. At the bottom the treasure is scattered around loose, and there's a big heavy chest that's rusted shut.
If they kill the Water Weird, it reforms in a couple rounds. There are ways to permanently kill it, but they might not know those or have access to them. They can't just grab all the loot in one round, and they'll have trouble bringing it up to the surface because it's scattered and the one big piece is so heavy.
Then they have to break it open, and if they're in the dungeon you'll roll for wandering monsters because of the noise and time spent. The coins will be corroded if they're copper (green) or silver (black), which may throw the players off a bit.
Likewise, in every dungeon (or every level in a huge dungeon) you shoudl have areas that they can't access right away. A door that requires a sequence of spells cast upon it, or a powerful monster they can't harm unless they have magic weapons (golems are great for this). They will remember those places and return to them later when they can break them open.
The PCs in D&D 3 and 4 are all ub3r k3wl superheroes. If you want to play that game, go right ahead. I'm not saying people can't have fun with it, or that it's bad. But I prefer a campaign theme of "ordinary folk presented with extraordinary circumstances" and so B/X and 1st edition fulfill that. 2E is a reasonable compromise, with lots of complexity and choices, but not such a huge power and number creep.
On the higher end of the scale, you could play a Final Fantasy RPG where the damage you deal is in the thousands and your enemies have hundreds of thousands of HP. It still takes X number of attacks to kill it. So from my perspective you might as well use small numbers.
Finally, a critique of D&D in general, because all the rules relate to killing stuff, you shouldn't be surprised if your players gravitate toward that. If that's what everyone wants, and you're cool with it, your job is to inject the things you think are cool, to build upon the bloodsoaked scaffold of violence that people like to play with.