I think the real problem with that rule is that there's really nothing special about the arrangement of your starting deck compared to the arrangement of your deck after any shuffle... I think people tend to think of it as different probably because the shuffling happened during the game setup rather than during the game itself. But what order your cards are in when you shuffle for the first time (usually at the end of turn 2) generally matters more than the starting order does in terms of luck. So if you are going to allow players to order their starting deck, why not allow them to order their first shuffle?
There is something special about the starting deck: it gets shuffled before you can make any decisions in the game. Randomness after decisions affects how you should make decisions and therefore adds a skill component to the game. Randomness before decisions affects how you can make decisions and therefore restricts a skill component in the game.
Another thing that is unique about the pre-game shuffle is that, generally speaking, it has a significantly lower set of choices than almost any other shuffle. Barring Heirlooms and Shelters (and a couple of other unique cases, like Nomad Camp), there are only four meaningfully different options for a starting deck: $3/$4, $4/$3, $2/$5, and $5/$2. And in many games there is no meaningful difference between $3/$4 and $4/$3 or between $2/$5 and $5/$2.
Starting with the first shuffle of the game, things quickly get much more complicated. Even if you opened Silver Silver (and even barring any 2nd shuffle purchases that would be gained onto the deck or immediately played or would otherwise draw/discard/affect the order of your deck, so that the order of the first two purchases don't matter), possible hands include (the third item is just the first two cards of the 3rd hand, which will include cards from the 3rd shuffle):
$7/$4/$0+
$7/$3/$1+
$7/$2/$2+
$7/$1/$3+
$7/$0/$4+
$6/$5/$0+
$6/$4/$1+
$6/$3/$2+
$6/$2/$3+
$6/$1/$4+
$5/$5/$1+
$5/$4/$2+
$5/$3/$3+
$5/$2/$4+
$4/$4/$3+
$4/$3/$4+
That's already eight times the number of choices you had in the initial shuffle, under the simplest of circumstances. I would expect (although I haven't done the math) that possibilities grow exponentially from there. Having to wait while another player decided this order would substantially slow down the game in a way that would be extremely unpleasant.
By contrast, even with Shelters or Heirlooms, the choices for the pre-game shuffle stay relatively simple. For most of the Heirlooms--Magic Lamp, Haunted Mirror, Pasture, and [usually] Lucky Coin--it doesn't matter which first shuffle hand they end up it. Pouch will sometime matter, but generally only if you are looking to buy $2/$2/$3. Where Goat and Cursed Gold land is more substantive, and does increase the number of options quite a bit. Similarly, which Estate is replaced by which Shelter usually will not matter, unless (1) there is a Way that makes Necropolis useful, or (2) you're going to open by buying a Victory card (a fairly unusual play, although conceivable with Tunnel or maybe Mill), and want Hovel in that hand.