I've come to terms with this. I now reduce all encounters by one or two levels/creatures from the guidelines in the DMG.
Combat is fun but one does not want to spend more than 50% of game time on battles ... gets boring.
This idea may sound good, but it's honestly somewhat flawed.
1) If you cut XP proportionally, then you're not really making combat shorter, you're just breaking it up into smaller chunks that may or may not make the game easier for the PCs in the long run.
2) If you don't cut XP at all when doing this, then you just plain are making the game easier for the PCs in the long run, and considering the fact that the game really isn't that hard for a decent party to excel at already that's not a good move.
Furthermore, you really can't judge it by the first few encounters. Above all, it's a new system. The first few encounters of a new system will be slow because the system is still being learned. You either have to get your PCs on the ball fighting the fight if they want to have fun playing the game, or, if they're not willing to do that, then either they're having fun already playing the game in an unfocused manner or they're uninterested in the game. Those may or may not be problems depending on your interpretation.
Also, 4e suffers a little from "shit happens" syndrome. In my last session playing my wizard, all my d20 rolls are as follows: 1, 1, 1, 2, 2, 7, 17, 17, 20. We were fighting dwarves and they were wedged in a doorway, so I was trying to Thunderwave them out of the way so our front-line could charge in and surround them. Even when I used my Wand Mastery to enhance one of the attacks, I only managed to hit with the power once (on a different attack, not the Wand attack). With a couple more hits the battle would have gone very differently.