The only thing I'll add to the discussion is if people think the cleric is "useless" in 4e, I honestly think you may be reading the rules wrong.
Here's the thing about the cleric, in combat, a character only has 1 thing they can do to heal normally...that's a second wind. And unless you have some other power that heals, that's all you get, once per encounter you can heal. From my experience that is simply not enough. The cleric has the ability twice per encounter to allow people to heal more....and there's just no substitute for that. If you don't see any value in the cleric, make sure your running the heal rules right, and make sure you are throwing proper encounters at your party. I'm not saying a 4e party can't play without a cleric, but there is a night and day difference in how that party has to play imo.
I will also say that the homogeneous play of classes is definitely an "on paper" problem. When I first looked at the classes I also concluded that the classes seemed very similar. But that has not turned out in play.
In one fight we had our paladin survive 3 rounds of combat with 9 (yes 9) creatures attacking him, our rogue killed one of the major bad guys by himself, and my wizard killed 5 minions with one shot. These are things that the other classes just can't do as well. The differences in 4e are smaller (for example there is no longer a huge disparity in AC between the fighter and the wizard for example) but those differences are no less important and class defining.
All that said, the OP's points are well taken. For example, I definitely feel 4e's combat is as complicated as 3e, and there is definitely more to track. Combats are also taking just as long in 4e as they were in 3e, at least at levels 1-3 where I'm playing now. Now...I'm enjoying the combats greatly, but it is not a quick and simple system for sure.