It's important to insist that the game master shall not use a rule too much complex (beware "creative" SW dev!). It's almost always harder to discover than expected even with smart people.
I can recommend Race for the Galaxy:
http://boardgamegeek.com/boardgame/28143/race-for-the-galaxy
Browse around the BGG website, read reviews, look at the top games, etc:
http://boardgamegeek.com/boardgame/438/scotland-yard
A more recent board game, also based in London but much earlier : London 1888 Beautiful board. Rules are relatively complex if I recall correctly.
http://boardgamegeek.com/boardgame/18/roborally
You play cards to program your robot and drive it round a course.
Also note that boardgamers consider Settlers to have once been something but that its time has passed -- they feel it has too much randomness due to the dice and can go on too long.
As for games worth considering, it depends on the types of people playing, their interests and how much time they want to devote to a game (as an extreme example, Twilight Imperium is supposed to be a deep, rich experience, but it takes 10+ hours to play).
Anyway, with that in mind, some suggestions I hope prove helpful in getting your collection started. All these games have entries at BoardGameGeek.com. There are reviews there and/or video reviews/playthroughs to get a feel for them.
Anyway, here we go:
Main Games
==========
7 Wonders -- on the lighter end, this one goes over well -- it's a gateway game, possibly the Catan of our time. All types of gamers are open to playing it. The game plays 7 (I think 8 with an expansion) and games can be played in 30 - 40 minutes each, so you can find yourself playing 3 games back-to-back. There are 2 or 3 official expansions to keep it fresh. Probably worth having in the collection.
Lords of Waterdeep: another lighter game which is a popular D&D-themed worker-placement game.
Dominion: perhaps a little bit more complex, but not by very much; it's a modern classic which popularized the deck-building mechanic. It's all about looking at a tableau of cards available for use during the game and figuring out which combos will enable one to succeed -- analytical types tend to be good at this. It has a lot of expansions (people shy away from the small ones and go for Intrigue, Prosperity and perhaps the newest/last, Dark Ages) and can play up to 6 or so.
Agricola: a classic worker-placement game that adds a bit of Dominion-like thinking about creating good card-combos. It has a lot of replay value -- and there are various expansion decks, etc. to add variety. It plays up to 5. It takes a bit of getting into though -- there's a learning curve to understand the various card-combinations in addition to learning which actions to take when.
For some people, this game is something of a cult.
Other more games that have been very popular lately include:
Tzolk'in: a recently-published ingeniously-fashioned worker-placement game with interlocking gears on the board that represent the movement of time (tzolk'in is the name of the Mayan calendar and the game came out in 2012, when that was in the news). You put your workers on the gears and the longer you leave them, the better stuff they'll be able to get or do. But you don't have many, so you'll need to pull them off in order to put them elsewhere. People are drawn to this one.
Battlestar Galactica -- a cooperative game with a traitor mechanic -- you're trying to get to Caprica but one or more players may be a Cylon. There's a lot of player interaction and it's tense. There are people addicted to this one. It has 2 expansions.
Space Alert: a very social game where you are trying to run a spaceship with the other players while various threats are coming in -- you talk through what you want everyone to do but play your action-cards face down and then, after the mission's 10 minutes are up (there are soundtracks for them, announcing where various threats show up, etc.), everyone reveals their action cards and you get to see if everyone did what they planned to do at the proper time or if your ship dies because someone didn't get power to the laser cannon when you were trying to fire it or didn't get to the ship's computer to jiggle the mouse to make the screensaver go away...it's a fun, humorous game and it has an expansion to add playability.
Galaxy Trucker: by the same designer as Space Alert, you quickly build ships by turning over and choosing tiles for various components while a sand timer is trickling. Then you send your ships out into space where they will encounter various threats and opportunities. The threats can damage the ship, leading to small--or very large--pieces of it coming off. There are expansions.
Race for the Galaxy, as suggested by someone else, is very good. People who play this seriously have the expansions (though they don't play with the "takeover" rules and perhaps "goals" -- they primarily use them for the extra cards). This one rewards knowing the cards very well, for combos. It helps to play the downloadable AI version -- just Google for Keldon AI. Adding the first expansion, The Gathering Storm, allows for 5 players (the base set goes 2 - 4).
A couple of older classics:
Puerto Rico as mentioned by someone else is good -- a classic, though not played so much these days, perhaps because it's older.
Caylus is another classic that doesn't come out so often these days, but it's very good -- it's the one that kickstarted the worker-placement genre.
I think all of these games above are pretty well-known in gaming-circles and many have a following and so should be good for starting off with.
Fillers
=======
Also, it's nice to have some smaller, "filler" games for playing as a warm-up or end-of-night game.
For Sale a game with 2 sets of auctions (first you buy a bunch of properties then you sell them) fits the bill admirably and plays up to 6.
Bohnanza: a card game about bean-farming. It works. And there are expansions/variants.
Munchkin: a small Steve Jackson Games game which is very popular and has a ton of expansions -- it keeps SJG afloat -- but some people loathe it.
There are some dice games like Martian Dice and the very different Liar's Dice which also might work.
Again, I think these are games that are well-known in gaming circles and so good for starting off with.
Buying Games
============
As far as buying games go, the online stores offer the best pricing -- two that many people like are coolstuffinc.com and miniaturemarket.com -- in addition to low pricing, you get free shipping at $100 or so and they each have a reward system, so you get subsequent discounts.
Or you might want to find and patronize your friendly local game store (FLGS), but most of them charge full retail, which can be 30% (i.e. $10 - $30) more.
I hope all this helps and happy gaming.
The game 'Container' is surprisingly awesome. The box is deceiving and doesn't make it look particularly fun, but there is a lot of replay value. You have to change so much of your strategy each game due to how others are playing the game.
Other good ones include: Tikal, Space Dealer, Saint Petersburg, Acquire, and Art Auction
Settlers of Catan
It's played as two simultaneous games of chess, with one player on a team playing white on one board and the other player playing black on the other. The twist is that any piece captured by your partner can be placed on your own board instead of a normal move (with a few restrictions).
The games aren't synchronized, and you'll need two chess clocks (one for each board) to keep things cracking along. The clocks are usually set to blitz times (such as five minutes per player), and either player on a team running out of time results in a loss.
http://www.chessvariants.org/multiplayer.dir/tandem.html
http://en.wikipedia.org/wiki/Bughouse_chess