A game that I like that I can play with people who aren't serious gamers is Fluxx. It's ever-changing rules make it entertaining enough for a strategy buff, but it is random enough where you can play it casually. A lot of fun overall.
It pretty much has everything Catan was missing. There are no dice. There is no random element, no luck involved. There are diverse options and strategies available. There are multiple ways to end the game and win.
If you pick it up, I strongly reccommend you get the expansion. You can download it for free at the Rio Grande web site, or you can buy it for $5 (saves you the trouble of printing it and cutting out the pieces).
The second game I recommend is called Shadows Over Camelot:
As you can guess, it's an Arthurian-based board game. What's cool about this game is that it's cooperative. The players play against the game. Up to 7 players, each player takes on the role of a knight of the round table, each knight has a unique ability.
From there you go on multiple quests and try to win victories for Camelot. It's a fantastic, addicting game. I always enjoy it. The cooperative style of play is a welcome break from the "screw-your-neighbor" type games.