The short version:
Quake 4: excellent
I just finished Quake 4, and I have to say, after getting into it, I really enjoyed it. I initially bought it because I loved Doom 3, and Quake 4 uses the Doom 3 engine and at least had input from their designers. The first few levels started out kind of boring (more in a mediocre sense than a bad one), but after a few hours things pick up. It's a very well done "space marines versus alien monsters" kind of game, and to stand out in a genre as vast as that one, I guess it's got to be pretty special.
The Doom 3 engine is put to extremely good use here. The graphics, environments, and special effects are all excellent—as they should be; the system requirements are still very high, in the same area as Doom 3. The railgun's (laser sniper rifle, for the uninformed) beam distorts space around it, areas around flames wiggle back and forth like the top of a hot car, and the dark matter gun (BFG with gravity) warps anything unfortunate enough to get in its projectile's path. Enemies dissolve in a flurry of green, uh, bytes in the same way that Doom's demons disintegrated into sparks like in the Blade movies. Your vision shakes around beautifully when you're stunned. Characters are all well-detailed, and lighting is realistic (except the stupid-looking flashlight, which is as poor as Doom's, presumably because of the CPU requirements of a more realistic flashlight).
Screenshots from GameSpot.
The things which I consider to be advances in gameplay that I first saw in Doom 3 are also here. Things like the amazing-looking and detailed computer displays really do help a lot with the immersion. Interactive computer displays with high-resolution text and live displays of the game world do much to suspend disbelief, much more than a four-frame animation set on repeat. Unlocked doors always have green lights, and locked ones always have red lights—I hope every FPS adopts this convention in the future.
People who hated Doom will be happy to know that most of the biggest complaints about Doom are not present, or scaled down a bit, in Quake. The gory atmosphere and dark corridors are still there, but the flashlight is far less important in Quake, and when you need it, it's attached to one of two weapons, so you're not at all helpless. Monsters never spawn behind you, and it's pretty rare for enemies to descend from the ceilings or walls, compared to the practically constant occurrences in Doom. It's somewhat less intense and jarring than Doom 3, which is too bad, since I really liked that, but for the people who found those behaviors annoying, you'll like Quake 4 better.
Boss battles were quite entertaining also. Some have interesting twists, such as an attack that can destroy the pillar you're trying to hide behind, and several have you having to deal with multiple other enemies at the same time. There are some levels scattered throughout the game, maybe half a dozen in total, where the gameplay is very different for a short while—perhaps you're in a hovertank or a mech, or you're on a tram mowing down the cars on the other tracks. And, in most levels where you don't get a new weapon, you get some other enhancement to an existing weapon—the ability to reload your shotgun with a clip instead of per shell, or homing nails for your nailgun. So, you've constantly got new dangerous things to play with. The only useless weapon is your "crap, I'm out of ammo" weapon, which is always a nice plus. Often you'll find yourself fighting with other people, sometimes medics and technicians that can make your life much easier if you can keep them alive.
I'd recommend Quake 4 to just about anyone who likes FPS games, even if you didn't like Doom 3... you can pick it up for $20.