We have max at 1st level and roll thereafter. I do give half rounded down if you roll bad, so a wizard cannot get less than 3 and fighter less than 5.
I do like the idea of advantage on the roll, kind of what @billd91 was saying, or the player rolls one and the DM rolls a secret one that the player can choose if they do not want theirs. I would let the player roll one in a cup turned upside down as the secret one.
Rolling is obnoxious and unnecessary, max at 1st level is a sensible mitigation of low level weakness, but I don't have a strong preference for max or average thereafter. Either is a fine enough balance point.
It's worth noting that a lot of 5e DMs may have monsters cast attack spells without adjusting the damage dice (they're balanced for players using them against monsters instead of the other way around), which can result in a skewed perspective of player hit point values.
I really like this idea, but I've never tried it. The big problem with rolling hit points is that, by RAW, you never really do so enough times for the law of averages to kick in until you get to very high levels. If you do it this way, you've rolled more dice for hit points by 6th level than you would in a RAW 1-20 campaign.