Alright, there are 3 big ways to make a monster more interesting.
1. Interesting mechanics.
2, Interesting tactics (and strategies).
3. Interesting environment.
Did I leave anything out? Oh yes. Just the one.
4. Interesting player abilities.
I often thing that there's too much focus on interesting mechanics, often at the expense of the other three items. For example, you don't need to have every monster be mechanically differentiated. Your orcs and your elves might have identical stats, and vary only in weapon choice, tactics, and lore. That's fine. Your players probably won't know or care.
So, I guess that's my first piece of advice. Don't over value mechanics as a tool for interesting combat. If you crack open a monster manual, that seems to be the base instruction. Every monster is mechanically different from every other one. But most monster manuals don't spend much time describing the monster's tactics or their environments (something that really should be considered simultaneously).
My second piece of advice is that mechanics don't have to be beneficial to the creature. They can be harmful, as in the example of the King of Sloths, which has a 1/6 chance of falling asleep after each turn (which is a good thing, otherwise the players would never have a chance) or a frenzied whip-tree that does 1d6 damage to itself each round of combat. These options make combat unfold in a dynamic way, and present interesting options. Yay.
Interesting tactics are frequently undervalued. Not enough words have been written about them.
Tactics are all the things that monsters can do that aren't explicitly listed in their entry. Pushing, tripping, disarming, grabbing, throwing, hostage-taking, cowardice, bravery, intelligence. I guess the morale score is an example of explicit tactics, and one with a long history. It's good for differentiating monsters, and diversifying combat.
Imagine a monster that is basically a HD 2 orc, except they flee as soon as one of their number is killed. Or, maybe the run away at the first sight of a well-armed party.
Intelligence is another one.
HD 2 orcs that attack random targets are much less threatening than HD 2 orcs that focus their attacks on the most vulnerable PC. Do they set ambushes? Do they taunt the PCs, or threaten them? ("Fight me one-on-one, paladin, or I'll order my archers to focus their arrows on your squire.")
HD 2 orcs that are motivated by gold will presumably act differently than HD 2 orc-simulcra that are merely beasts looking for meat, or for a way to protect their nest.
Anyway, those are more like broad strategies. Consider the more specific class of combat tactics. This is one that has a long history in old-school games. Sure, the HD 4 ogre doesn't have any special abilities explicitly listed, but they're implicitly very likely to pick up a table and try to knock all the PCs over simultaneously. Or reach up and pull down the roof. Or grapple* you and attempt to twist off your arm like a chicken wing.
*Grappling an ogre is such a bad idea. It's like a kid trying to wrestle an adult. Even if you're one of the strong kids, the ogre is stronger.
Anyway, the take home message is that monsters aren't limited to the stuff on their character sheet. Harpies might try to fly away with everyone's spear, and then return later after licking their wounds. Lake drakes will capsize your canoe.
Interesting environments have the same advice as interesting mechanics: make sure to give players both beneficial and harmful environments. Elevation. Treacherous footing. Thorns. Underwater. Poor visibility. Ambush opportunities (let your players engineer their own encounter). Light sources.
And lastly, remember that a great deal of the fun of a combat comes from the players. If you are throwing 30 orcs at the party, you don't need fancy mechanics or environments--30 orcs against a party of level 2 adventurers isn't unwinnable, but the players are going to need to get creative. Retreating until they find a defensible position. Searching their inventory for that potion that they forgot that they had. Combining their character abilities to make beautiful music together.
I know my last point seems paradoxical. "You don't need to make combat interesting because your players will make it interesting for you." But this point is only really useful if your players are forced to exploit limited resources, such as the environment, their daily abilities, and their limited-use items.
That's one thing I didn't like about Fourth Edition--combat usually followed the same pattern. You use your Encounter powers first, then your At-Will powers. If you thought you needed them, you'd bust out your Daily Powers. The only decision point there was whether or not to use Daily Powers; everything else is semi-scripted. And because 4e didn't like giving out expendable items (unlike Numenera), there often weren't many decisions to make on the inventory-side of things, either. And so combat often unfolded in similar ways and along similar combos, like chess. (Which is fine; I like chess.)
There are good reasons to dislike daily abilities (or the Vancian spellcasting system). But it does create a lot of challenging decisions (should I use X, or save it for later?) which I personally enjoy as a player. There's another dependency here, though: the game must be challenging/lethal enough that players are required to use their expendable resources, instead of hoarding them.