The halfling (Pansy) runs up behind a tree and tries to hide.
Sorry, say I, the tree provides only partial cover.
"But I am Small!" says Pansy. "I am only 3' 8"!"
Okay, but then, how large is the tree? I mean, the person's size is not important, it's his size compared to the tree, right? In a game where a human plays with ogres, would humans also be allowed to to hide behind trees in combat because they're smaller than others?
This aside, assuming a tree with a relatively large trunk but still your average tree (much less then a 5-foot diameter), I would not allow it. The opponents see the halfling move behind the tree and can lean on one side and the other to look at the halfling. In game terms, you can draw a line of sight to three and perhaps all four corners of the halfling's square. He can't hope to benefit from superior cover IMO. If the halfling had been hiding out of combat, I'd allow a stealth check (normal cover enough). In combat where people can see him move behind the tree, no.
This being said, I often play with cover bonuses as DM. For one thing, I sometimes vary my cover bonus to defenses between +2 and +5 depending on how I feel the cover acts for a PC. E.g. this is not quite superior cover, but you get +3 or +4. Also, the player's intentions are important. If indeed he tells me that his PC hides with his back against a large rock, and he's a halfling, and the rock is bigger than him (larger than a 5-foot square) and the angle of view from opponents is not good (e.g. they're behind the rock), then I'd most probably allow for superior cover or more, total absence of line of sight. However, if the PC moves behind the rock and says nothing, then he's not attempting to use the terrain to his advantage, he might have less cover.