We first clocked onto Carcassonne more or less by chance. We were having our second Warps get together, at Anton's place. On a whim, I made my first visit to a games shop in probably 10 years, Dungeons and Starships in Digbeth (now defunct I think). There was a game going on around a large table in the back half of the shop. They didn't look up. If you've read High Fidelity, you might recall the description of the record shop and how it's kept deliberately gloomy to deter casual trade. Dungeons and Starships had that feel, but nonetheless the chubby, bearded young chappy behind the counter, resplendent in purple shirt, was friendly and polite. I told him I want a game for gamers who hadn't gamed for ages. He went over and consulted briefly with the gamers, and pointed me at Carcassonne.
And they were right. Carcassonne is a top game. It's rules are simple, but subtle. I've played it with four, three, and two players and it works equally well in each case, although what makes good strategy changes. (That's not always the case, a game like Cosmic Encounter, for example, stinks up the place with two or three but comes alive with five or six.) You can play the game with a variety of strategies, there's a balance of luck and skill, and it rewards cooperative play at least to a certain extent.
Carcassonne is a tile laying game, so you build the board as you go and it's different every time. Each player, in turn, draws a tile from the box. Each tile features some combination of a road, a field and/or a city. You play your tile next to the tiles already on the table, matching up the features. You score points for completing a road or a city, or controlling a field. When all the tiles are placed, the game ends. A variety of expansions add extra tiles or add new rules - increasing the score of a city, say, but increasing the risk of not scoring at all.
If you're a lapsed gamer, or you want something more interesting to play with your kids, give it a look.