I've never been a terribly hardcore R.E.M. fan, but my roommate in college turned me on to some of the older stuff, and I really got into Life's Rich Pageant, which came out when I was like 13 or something.
The last album I bought though was Monster, which I think came out in '94. Between the meltdown of good radio and demise of MTV, that certainly caused an exposure problem for them, but I'm not sure any of those records jumped out at me anyway.
But I picked up Accelerate on the Amazon MP3 store and I'm digging it. Most of it doesn't really grab you at first, but after a few listens it's pretty good. The tracks that did jump out at me from the previews were "Until The Day Is Done," which is I think a commentary on the war or perhaps the general disenchantment a lot of people have with the country. "Mr. Richards" is also very good, and I think it's an indictment of criminal CEO's or politicians or George Bush. I'm not sure, but I like the song.
On the radar, and crossing my fingers for coolness... Portishead's Third and a new record from Armin van Buuren.