This came up when a PC in my game was immune to the Frightened condition. They said that the intimidation should fail since it relied on fear. How do I rule this?
The rules on the Intimidation skill state:
Intimidation. When you attempt to influence someone through overt threats, hostile actions, and physical violence, the GM might ask you to make a Charisma (Intimidation) check. Examples include trying to pry information out of a prisoner, convincing street thugs to back down from a confrontation, or using the edge of a broken bottle to convince a sneering vizier to reconsider a decision.
It says nothing about the Frightened condition so by rules as written it makes no difference. A GM could rule that a character immune to being Frightened would get advantage on any rolls against being intimidated but that is at their discretion.
Keep in mind though that intimidation isn't simply a matter of making someone else fear you. Not being afraid isn't the same as being reckless. A character might back down when intimidated because they know they might be hurt or killed otherwise. Consider the case of a town mayor with 20 poorly armed and trained militia members at his back being intimidated by a bandit leader with a hundred well armed and seasoned bandits at his back. Even if the mayor is immune to being Frightened he could still see it would end badly for him and his town if it came to a fight.
"Frightened" is a specific condition in the game rules that simulates acute fear - your hands are shaking, you can't do things, and you definitely won't move closer to that scary thing. It is a state more akin to a phobic episode or a panic attack.
The bouncer at the tavern is intimidating - you can tell by his size and strength and gaze that he's an experienced fighter you better not mess with unless you want a fight. But you can still walk around the bar, even talk to the bouncer, unless you attempt a specific action that makes him tell you to stop. The bouncer needs to be obeyed, because it's obviously a bad tactical idea to fight him, but you don't lose control of your bladder just from looking at a large human that's working at a tavern.
A bathtub full of tarantulas or a ghoul climbing out of a morgue drawer - those things are frightening - they trigger deep seated phobias and superstitious fears and you may not be able to function normally around them.
A lot of GMs will allow intimidating someone clear into the frightened state, but that isn't really the rule as written, it's more of a convenient mechanic to grab when say, a peasant takes a swing at a necromancer.
I would say your PC is immune to the mechanical effects of being "Frightened" but unless he's a berzerker barbarian or something, he should still be able to tell when something is intimidating in the sense that it would be a challenge to fight.
It probably wouldn't be out of line to give him, say, an insight check to see if someone's attempt to intimidate is a bluff, though. It sounds like that type of character would not be afraid of paper tigers.