You need to play with the 'cities and knights' extension. It makes the game more complex. Also try the board game Puerto Rico, which we're just getting into but seems pretty awesome.
In my experience --- and I am from Germany ;) --- The top games at the boardgamegeek are too complex as first games.
Settlers, Bohnanza and Carcassonne are excellent starters into the world of boardgames. Geeks will want to graduate to Caylus, Puerto Rico and the like later on.
Does it reduce the luck element a little? We have the base game and the Seafarers expansion, and we got a little bored with it. The key seems to be picking the right starting positions, the rest is mostly plain luck. (and relentless trading of resources)
I think they redesigned the game recently, so it's possible the new version of the expansions won't work with our original edition anyway.
These days, we're mostly into Puerto Rico, Ticket to Ride (various editions), Carcassonne (also somewhat luck-based), Power Grid/Funkenschlag and Agricola.
I've played Cities and Knights, and I like it a lot better. The progress cards let you affect trade, other players, or speed development, and offer some additional strategy. The aqueduct ability (#3, paper) even minimizes the effect of a dice-induced resource shortage. The constant threat of barbarian invasion always results in a race for knights, and the accompanying strategies of trying to one-up the other guy.
C&K basically gives players more ways to affect the game's outcome through actual decisions (more of which are sorely needed). I haven't played it myself so I can't say how effective they are, but it's a step.
You should buy such extensions if you have played the basic game a lot.
Games also last longer with this extension, count on 3 to 4 exciting hours.
Since I'm on hackernews, I've always wondered when this game would pop up and what other board games you would advise. I'll have a look at Puerto Rico asap.
Board games depend a lot on taste. Are you more into eurogames (great mechanics, generally light on theme) or "ameritrash" (great theme, generally complex mechanics)? Do you want a heavyweight, longer game, or a lighter-weight, short game? Are you a fan of luck in games, or would you rather it was more skill-based? Do you like diplomacy as a game mechanic?
Also, most (good) board game shops have an open play night where you can go in and check out whatever you want. This makes putting $80 down for that copy of Agricola much easier.
If you're in the greater Seattle area, Uncle's Games at Redmond Town Center has a game night on Fridays. They're also the best game shop around, imho (although I might be biased, they know me by name).
I can seriously recommend Agricola. It features a very novel gameplay concept, and to make it even better, they have different sets of cards to adjust the games difficulty level. I've played Agricola about 10 times or so now, but I'm eager to play it more often. And there's not a lot of games that can do that.
Seriously, though. It was just okay. The game always ended just when things were getting interesting.