I think a good challenge really relies on your PCs.
I mean, if your PCs are all built as warrior/tanks and don't care anything about social encounters, then the most subtle, well-crafted social encounters are going to be completely lost on them.
In the game we played today, for example, my cloistered cleric faced an interesting challenge that I really appreciated. Few dice were rolled. We were to apprehend a villain that had committed crimes, and his reward was a substantial amount of money to us (1st level PCs). My character is a mendicant, meaning he is a begging priest, who carries only a staff essentially. So, while he's "good" in the medieval sense of good, that implies that it's for the greater good, and doesn't necessarily coincide with our modern interpretation of good.
Anyway, we confront the guy and he offers to pay my character the same amount as his reward, plus a promisary note worth an equal amount. I struggled with this for quite some time, but under the circumstances it seemed like the best outcome, since I'd be able to feed twice as many people, and this man had already endured much (he was fleeing the country). So, that was my course of action.
Point it, if my character were a Barbarian, I'd probably have just smashed his skull in, so there wouldn't have been much to the encounter other than that.