I was actually playing around with using the following:
d4 = 1d3+1
d6 = 1d4+2
d8 = 2d3+2
d10 = 1d6+4
d12 = 2d4+4
Max HP = normal max, Min HP = half max, average = 75% max.
Same range as "add half if you roll less than half", but distribution is different, I think.
I did a game with "if your roll half or less, add half", but that meant the wizard always got at least 3/4, while the paladin might only get 6/10, and just seemed to benefit the wizard more than the paladin.