I am not sure of the mechanics, might need to be played only online or may not work at all. But to address the frustration that players express with being dealt poor hands, what if various two-card combinations were pre-arranged and given to each player. (Note this would required perhaps two or even three decks for reasons that I think will become obvious.)
Both player are given the exact same set of two-card hands and everyone knows what they are. There might be a standard set: all pairs and even some very bad hands. Players choose from among these hands and once played, they are eliminated: obviously you can't just play AA each time.
The cards from an intact third deck are dealt as usual. Note that this means some hands that are not seen in standard holdem might arise: not just 5 of a kind but even 6 of a kind and the hands would be ranked by probability just as hands are ranked now.
This variant has 3 important new features: 1. The optimal choosing of very good hands -- probably a bad strategy would be to start with the top pairs and exhaust them too early 2. The need to remember what your opponent has played (but this would perhaps only be revealed if the hand went to the end -- if you fold, neither player would know what hand had been played and thus removed from the the reservoir of hands although interestingly, based on the flop and your opponent's behavior, you might infer what hand he had chosen. This adds a type of strategy that is not present in holdem although of course it is related to inferring cards, but this inference in this variant has lasting consequences 3. While there is still luck, the common cards are the only thing the players could "complain" about because the most important hole cards are completely equally given to both players.
Two other points: I guess multiple players could play this game also but probably best suited to heads up. And finally, I will frankly say that a major potential source of cheating by the dealer is eliminated. He would not know what is dealt to each player since only the players make the choice. The dealer could be as good a mechanic as Scarne or Ricky Jaye and as far as I can tell, this would make no difference at all, at least in the early phases of the match -- I guess a very exceptional mechanic could eventually start dealing boards that based on the cards expended would be better for his confederate or, if the confederate could accurately signal which hand he had chosen, the board might favor the confederate. But I think this variant would severely curtail the opportunities for cheating (which is not to say that they are common).
Could holdem be played in this way or would it be impractical because of the need to set up? Seems like for very high buy-in tournaments, reducing luck not to mention the other features listed above might be attractive.