My players and I like to have fewer, harder combat encounters, as we'd rather be roleplaying than working through combats that we know the PCs will win.
It seems hard to arrange for this in 5e. I calculate the XP thresholds for my three PCs, and build a hard encounter, and either (a) they are wiped; or (b) they win, but it takes ages and ages because enemy HP is so high.
How can I build hard but winnable encounters which don't drag due to very high monster HP values?
From what you've said so far, you think like most DMs. This isn't surprising - it's how the modules and books train you to DM. You design encounters based on the party strength, balancing monster ratings with party level, and then come up with excuses for the party to enter that encounter. You can keep that going for a long time but eventually it becomes tedious for the DM, who is more a calculator than a creative writer, and boring for the players, who know that every encounter is calibrated to their characters.
What's the alternative? It's simple. Start with the monster . . . something well beyond the capabilities of the party. Give it the resources befitting such a creature - not just a lair but territory, not just treasure but an arsenal, not just minions but an organization. Give it an appropriate set of goals (and here's an important point, give key minions their own goals, not all of which are necessarily parallel with the boss's). And give it a few enemies, with their own organizations and goals. Once you have these basic concepts fleshed out in your mind and on a few spreadsheets, stop being the DM and start playing the monster.
As the boss, deploy your resources through your territory, keeping your goals in mind. Create strike forces and put them to work - perhaps the players end up involved in their attacks, perhaps they just hear about them as news and rumors. Design defenses for the territory and man them appropriately, using only the resources that you already decided as DM were available. (In other words. quit making up the numbers according to what balances the encounter.) Come up with a general plan for how the boss is going to accomplish his goals.
When game time starts, your players should quickly figure out that the encounters are no longer calibrated. Some encounters they will just blow through, while others they will have to run away from. (This can be hard for players that are used to every encounter being winnable.) It might take a few sessions before they realize that they have to figure out ways to win "unwinnable" encounters. The thief will have to use his sneaking skills to do more than just get in a surprise round - he'll have to gather intel to bring back to the party for strategizing. The players may have to find new allies (which means more role-playing opportunities and larger stakes in those encounters). They may learn to set traps and ambushes that get more than just a round of surprise. (Be prepared to expand the price list beyond caltrops, holy water and hunting traps and the few poisons listed in the DMG).
One lovely side effect of DMing with this mentality is that even the easy encounters will make your party nervous, simply because they can no longer assume that every encounter is winnable. I've seen my players (@3rd level) run in terror from two goblins, just because the goblins weren't supposed to be there and they thought that their entire plan was already compromised.
When you first start, you might have some trouble spreading the boss' resources realistically. There is a tendency to put everything in one central lair. But that's not a great way for a boss to work - there are good reasons why armies have multiple bases, kings have multiple castles, corporations have multiple factories, etc.. Think of all the different activities the organization has to accomplish - not just plundering and evil, but the procurement of supplies, feeding of minions, meeting their spiritual needs, engaging in trade and diplomacy, even recreation. A lot depends on your boss' goals, but he'll certainly have a lot more going on than will fit in one dungeon. And each of these activities can become a target for your players - or the means of infiltration.
One final warning: this method isn't for every DM. It requires lots of work up-front, which is balanced by the fact that it takes very little work from game-to-game. It is also not for every set of players. Not all player groups really want to make plans or deal with the inevitable failures that occur. You will have some games in which the players simply roll through everything, and some games where they just butt their heads against the wall. But when they finally take down your boss, the satisfaction that they'll feel will be better than any you've seen in a RPG.
I'd suggest making (most/some) encounters about something other than survival of the heroes. "Winning" an encounter than means something other than mere survival, and you can have monsters that seem weak against the players, but might still achieve their goals. For example, monsters might try to flee, or threaten civilians, or destroy something important (think a fortress' entrance doors), there might be a time aspect (I recently had a nighthag getting her treasures out by a portal; every turn, she took something lootable. Reinforcements arriving, if the players are made aware of that beforehand, can also act as a sort of timer).
If you want interesting encounters, force the players to be creative: Make it clear that the opponents are vastly superior in combat, then watch them come up with something of a plan, like an ambush. The stuff players come up with to beat a seemingly unwinnable combat is often more interesting than the combat itself. Give the players choices, and encourage finding even more possibilities.
Thirdly, you might think about abort criterions if you think the combats are too long. When might a combat encounter end, and negotiation/flight begin?
Twice in your question, you mention enemy HP is too high, so lower it.
The HP listed for each monster in the MM is the average of their total hit dice. For example, a monster with 4d8 HD would have 18 HP. Per the table on page 274 of the DMG, HP is the main factor in challenge rating, so be sure to adjust the CR of the monsters if you adjust their HP.
And, since you mentioned you want it to still be 'harder' without adding more enemies, you can always increase the base damage of your monsters. Again, the table on DMG274 gives you a good ballpark on damage output.
If you reduce the HP of your monsters by one row in the table, it's easy enough to increase the damage delt by one row, too.
Say you have a CR1 monster with 80HP and average damage of 13 (2d8+4). If you reduce their HP by 10, it's defensive CR is now 1/2. To offset that, raise the damage by 1d8 (3d8+4) so it's average damage is now 17.5—an offensive CR of 2!
Instead of a small number of very high HP monsters, use a large number of low HP ones. 10 goblins has the same HP as an Ogre but will seem to go down faster since the PCs are removing one or two goblins from the fight each round. Visible progress will keep the players more interested and involved.
More enemies does mean more incoming damage to the characters, so be careful.
Instead of 10 goblins, use 4 goblins with swords, 3 goblins with bows, 2 wolves and a slime. When the players have to think tactically, to prioritise targets, the combat will appear harder and be more interesting.
Since there is more damage incoming, give the players ways to avoid it. Scatter the battlefield with pillars and rocks and trees to hide behind. Put down some mud, to slow combatants (and to allow use of attacks like Shove and Knock Prone).
Make the enemies do things other than "do damage". Shove PCs into mud, knock them Prone, web them, put them in darkness.
These might seem like combat will take longer to resolve, but the trick is that if you use more varied tactics but use less powerful foes, then the combat will go quicker but the players won't notice, because they are focused on the tactics.
A combat that is just "Roll to hit. Do damage. Knock a bit of HP off. Repeat" seems much longer than it is.
