I might suggest then making sure that there are ramifications for fighting. By this I don't mean punish players arbitrarily for choosing to fight - it should be an option open to them, make sure they get just as many rewards/XP, which ever way they choose to solve a problem, as long as it's done appropriately.
Rather I mean make fights have consequences later on, in the narrative, or ongoing consequences for the players. For example, your PCs are involved in dubious black market dealings, and and meet a corrupt Guard Captain. A fight develops for some reason, your PCs might Kill the guard captain and his thugs, injure him and he gets away or be beaten by them - three options. If they kill him, this could have serious consequences, such as blackmail by nearby blackmarketeers, other corrupt guards looking to kill them, and so on. If they Let him live or he gets away, perhaps they run into him later on during a court intrigue part - he won't say anything because you have the dirt on him (he's corrupt), but he will try to make your PCs lives difficult. Finally, if they get beaten, perhaps they're taken to a prison and arrested for affray, which could damage their reputations, or he could blackmail them to do some dirty deed for him. All are possibilities, depending on the outcome of the fight, rather than just making fights where the PCs just kill everyone and move on, or have the PCs meant to lose, it could go either way.
Poisons, or other ongoing effects, can also make PCs feel the effects of combats outside of the brief fight. A fight against a few inept assassins might be easy, but if one or two of the party gets poisoned, the effects of that fight can last for a while, and spill into other parts of the story. If you can't find a poison listed in your system that would have after combat effects, make one up. It could affect their interactions with people, perhaps they'll have to try to find an antidote for it and so on.
It's also possible to have more narrative combats, with less dice rolling. For example, it sucks if your PCs want to do a quiet/stealthy mission, such as an assassination, under the normal rules, as it takes so much effort to kill any enemy, there's no way to make it feel quick and silent. So then, you have to change the rules around to make it possible. A rouge like character might never take down a guard, even from behind, in a single shot - so instead, make up rules for instant killing, if the PCs do it right. Give them a good bonus to hit, and make them able to instant kill/stun most of the time, so they can have the movie like feeling of sneaking through a building, taking out the guards. Get them to roll a dice to do it, but have them explain how they're doing it (I sneak up and slit his throat quietly), roll a single to hit with bonuses, and let him get the kill. Don't make them too good at early levels, but make it possible to do.
As for what critters to use... well, I'd need to know a bit more about your settings to give much imput on that. It sounds like you're playing a more realistic game, and mostly dealing with humans only. I prefer a bit of a fantasy theme, which allows a lot more breadth for introducing monsters and gribblies. Just having humans can work, but it's easier working with a larger range - when you can send a giant against someone, it can make for a much different fight than sending a bunch of goblins, but it's hard to get the same epic feel fighting against a single, powerful human. If you have magic in your setting, that can be used to great effect for making fights interesting and unique. Any setup that can make your players think and have to plan to take him on can work well - a sorcress in a maze of mirrors, who can shift them around so the PCs are always guessing where she is, A din-jinn who can transform into a whirlwind, a wizard who can reverse gravity and so on. If just with basic humans though, you have to use a lot more description, find a way to let the PCs know how tough an enemy is without just saying it straight out. A plate armoured knight should be hugely tough to take out, especially if you've built him up in the story line a bit, while a street thug should be reasonable against some things, but fold easily against most combat characters.