I like the initial post. It brings up some good points. Here's some short responses.
1) Decisions only understandable through experience: I think this is inevitable to a certain extent in a game like D&D. In WoW, getting a hundred combats under your belt isn't that huge of a time investment. In D&D, its enormous. By the speed at which I tend to play, that's about 25 game sessions, or 6 months of aggressive gaming.
There are some ways you could work to fix this for newer players, however. Feat retraining is one big one. I'd go further, and advise DMs to help new players in the following way- before they even look at the PHB, tell them to give you a character concept, in words, not in game stats. Then have them build it as best they feel they can. After a level or two, let them completely recreate their character, as long as they attempt to stay true to the concept. Once a player is experienced, they won't need this assistance, but its a good idea for new players.
2) Speed of character creation. I think this is going to be faster in 4th, due to skill points probably going the way of the dodo. In my experience, that's always a hangup for new players. Further, the example level 1 characters can help speed up character creation for a new player. I know a lot of us roll our eyes at these, because they often feature sub optimal choices. But they're really great if they give sample gear to purchase, as that's another place players get hung up.
For advanced players, who are really the only people who should be building higher level characters, the time of character creation is less important because they know how to do meaningful things with that time. I've never had anyone complain about the time it takes to put together a 10th level character, because they felt that the time was spent doing something fun.
3) Regarding the speed of advancement at early level. I half agree with you. I do feel that it might be nice if early level advancement were quicker. However, I think that to do this, you need to make early level advancement a little less important. Right now, going from first to second level is a huge increase in power. I wouldn't want to just hand that out after session 1. If early level advancement were a little less important, I'd prefer it go faster.
Right now, D&D handles early level "rewards" with gold coins that let you buy all the gear you wanted to buy at first level but couldn't afford. That's not a terrible system, but I can see why people might want a shift.