Spice up encounters with dilemmas
Power gamers and story gamers have different priorities. As a gross generality:
- During combat, power gamers are concerned with making choices about tactics.
- During combat, story gamers are concerned with making choices about character dilemmas.
To entertain both, fill your combat encounters with interesting tactical choices and interesting character dilemmas.
You already know how to make combats tactically interesting. To make combats interesting to story gamers, add an interpersonal dimension. What are the issues that are important to your story gamer players (and their characters)? Push those issues.
Example:
The party encounters a horde of goblins in a dungeon. You have an encounter set up that will capture the interest of the power gamers. Now you need to make it interesting to the story gamers, like "Bob," the player of the paladin.
You add a dozen prisoners (all minion NPCs) tied up and spread out over the map. The goblins have them held hostage. A goblin can choose to perform a coup de grace on a prisoner instead of attack the PCs. A prisoner will move by themselves as long as he or she is adjacent to a PC (for protection), but provokes opportunity attacks as usual.
So now the paladin has to figure out how to save the prisoners. It's not just a combat anymore. It's a choice between helping his friends fight and helping the prisoners get away. It works because the paladin's "defender" role is thwarted by all the crazy movement required to move the prisoners.
Reward ALL the players for each rescue, with role-playing and dialog and effusive thank-yous from the grateful hostages. Reward them all with XP, too. This can be a small, flat XP award per hostage or you can treat the encounter as a minor quest.
Push Consequences
Story gamers love consequences. If your games are a series of barely connected combat encounters, the story gamers will grow bored.
Consequences glue player choices together. What you decided yesterday influences what happens today and tomorrow, for good or for bad. Story gamers want that cause-and-effect in their game. That connectedness is story.
You don't have to spring consequences on a player by surprise. It's often better to let them know exactly what will happen if they decide X or Y, and let them choose. Just make all the paths meaningful and interesting. Make the choice hard.
Example:
The paladin and his party have cleaned up the goblins and freed the hostages, but the goblin leader escaped. The surviving hostages tell the party, "You have to help our Baron! He was captured with us, and taken away to be tortured a little bit ago!"
Does the party chase the goblin leader or go rescue the Baron? Make it obvious that the paths lie in different directions. Make it obvious that the Baron will be tortured, possibly killed, if the party does not rescue him immediately. Make it obvious that the goblin leader will escape if not pursued immediately -- perhaps to go back to raid the unprotected village as punishment for the attack on his tribe.
Then the paladin and the rest of the party have a tough decision to make. The story gamers will eat this up.