I'd like to add a few extra things to the other answers here, which are all good answers as well, but don't cover the whole feel and experience of the differences.
Rules as Simulation?
3.5e attempts to simulate a world with numbers and rules. If you have X strength, you can lift Y pounds. A given weapon or spell does exactly X damage to any opponent's HP. A roll of X on your jump check will send you exactly Y feet. Etc.
4e does not do this, and if you come into it thinking that it does, you will be confused, befuddled, and probably angered. Instead, 4e uses a cinematic simulation, and numbers are all relative, instead of absolute values.
For example, the basic unit in 4e is not the "5 foot square", it is "the square". How big is a square? Well, the books will tell you that a square is usually 5 feet. But it doesn't have to be. When my players hit paragon level, I announced that all squares were now defined as 10' squares instead. The rules don't change, but the feel does... everyone suddenly felt twice as fast, twice as strong. Descriptions had to change, with a lot more moving about, a lot more "controlling space" to define what they were doing. And then, at epic level, I graduated them to 100' squares. The math didn't change. The battlemap now drew villages instead of streets, but still worked as a battlemap. But boy howdy did the feel and scope of the game change... big time.
HP means different things at different levels, due to the "Minion/Elite/Solo" system. The rules don't tell you this, but if you look at it close enough, you can see that a normal level 10 monster is the same thing as a level 5 elite monster. The defenses adjust, so that level 5 characters can actually hit it. The HP adjusts, so that combat doesn't take all day (note: some argue that the HP doesn't adjust ENOUGH, but you can tweak that with practice). But the level 5 elite has more things it can do in a single round, and is a lot more threatening than a level 5 standard monster. The challenge has significantly increased, without being impossible-- it's still fun. My simulationist players simply accepted that the level 5 elite got more attacks then the level 10 standard monster because the level 10 standard monster is just faster than level 5 characters.
Thus, everything becomes relative. You start thinking less in terms of "I'm a level 6 characters fighting a level 8 monster", and start thinking "I'm fighting a monster two levels higher than me". Your level doesn't indicate a mathematical, gameplay based power level, as much as it defines a NARRATIVE power level. What is your impact on the world? At heroic level, you save the town. At paragon level, you save the kingdom. At epic level, you save the whole world, and maybe even some other worlds while you're at it.
Another thing that drove my 3.5e players nuts was the idea that the numbers for monsters and the numbers for PCs have no real relation to each other. A monster might get hundreds of HP at epic level, while PCs might have HP merely in the dozens. You cannot build a PC and run it as a monster. The math just doesn't work that way.
Rule Clarity
That said, things in 4e are a lot more clearly and concretely defined than 3.5e. In 3.5e, there are many, many, MANY rules interactions, and quite a few of them are ambiguously worded or confusing. You can really get into the fun of exploring all the rules of 3.5e, even outside the game, just to see how far you can stretch them-- the result being works of art like the legendary Punpun, or the Hulking Hurler.
4e's rules don't do this. Interactions between statistics and rules are kept to an absolute minimum, in what is called "Exception Based Rules". There is a simple set of rules that just plain work, and then when you get powers and abilities, these powers will generally create a SINGLE exception to the basic rules, which are all clearly and precisely defined.
As a feature of this, it's a lot easier to simply put everything you need to run a character, or a monster, right there on the page in front of you without having to flip between books and pages to find out exactly what a spell or ability does. The rules are clear, and compact!
I have DM'd both 3.5e and 4e. I have had hours of rules debates about 3.5e. I have never had more than a cursory "Ah, I forgot the difference between a close burst and a blast for a moment there" in 4e. It just works.
Where is the Game, in the Preparation, or at the Table?
Extending from this, in 3.5e, there was a lot of fun involved before you ever sat down at the table. My players could spend hours, days even, designing a character, going through splatbooks left and right looking for the perfect combination of feats and classes.
When we finally had our game session, combat was often over before it started. My 3.5e players would sit around the map, studying the layout, seeing the opposition, and then crafting an intricate plan and sequence of spells or abilities or item usage that would probably end the combat instantly, or at least without any surprises. Once the plan was in place, it was simply a test-- did the strategy work? If yes, we win. If no, time to come up with a new strategy. In 3.5e, my players practically ignored the dice, because they would manipulate bonuses, buffs, and so forth, such that if they attempted it, they knew the dice would work 95% of the time.
In 4e, character creation is actually pretty simple. Yes, there are some tricks to it, and it is possible to make simply bad characters with certain combinations (which are easily solvable by reskinning, see next section) but in the end, if you've got DDI, you select some things from a list, and start playing. There's not a lot to tinker or pour over. My players said it was BORING when we first switched, because of this.
But they soon changed their minds, because once play started, THEN the game began. The actual combat felt like chess, with precise positioning being key and the flow of battle constantly changing. Everyone was moving all the time, they had to dash to save each other, and while plans could be made, the plan would never be the only thing that mattered-- dice were always there to mess things up or change things around.
The Fluff is what you want it to be, the Crunch is all that's written down
Because of the "simulationist" nature of 3.5e, if you wanted a specific character story and background, with a specific look and specific weapons, there were rules for that. If you wanted a Halfing Wizard wielding a Greatsword, there are rules for exactly that... you might suck, but that's what you chose.
In 4e, it just feels so much easier to reskin. My player discovered that the best builds for certain classes didn't match the story they wanted to tell. So we stuck what they wanted on top of a build that worked. No one cried foul, because there was no real simulation to screw up, just rules for what made for a fun combat at the table. One player was a necromancer in the game, but his character sheet said rogue (albeit with the ritual magic feat). Another player was a halfling knight riding a wolf, but his character sheet said goliath barbarian. It just felt so easy to reskin when the rules
weren't tied so heavily to the fluff.
That's not to say that there's NO fluff attached to the rules. If you didn't want to be creative, you could still stick with what the character sheet said. Powers and abilities give a general jist of what they're doing, and so on. It's just easy to reinterpret.
DMing is easy
Here's the biggest change in my opinion, and the reason I will never DM 3.5e again, and am reluctant to go towards 5e.
In 4e, preparing for a session as a DM is the easiest thing in the world. Instead of spending literally hours, as I used to, preparing stat blocks and doing all the math for the enemies... now, I just focus on writing the story. The stat blocks for every monster in the world can fit on a single business card: http://blogofholding.com/?p=512
In my experience, when the DM is happy, players are happy. When the DM has less work to do, the player experience can be that much richer.