I would also recommend Settlers. Its pretty well balanced, its easy to learn and straightforward to play. Our group plays tons of board games, and Settlers stayed at the top of the heap for a long time.
"Torres" is another German game for 2-4. Its a strategic building game, with the theme that the players are princes adding to the castles of the kingdom. Despite being a challenging game and a lot of fun; its strangely non-conflict oriented, which is good for certain gamers.
"Through the Desert" is an area-enclosing game; we call it "Pastel Camels" because of the 100's of small, attractively colored pieces. ;-) Despite having lots of pieces, its very straightforward to explain; in some ways its like a multiplayer version of Go. Enclose area; keep others from enclosing more area than you.
"Carcassone" is our current favorite. Its a tiled building game; draw a tile from the box, add it to the board and then decide how to occupy it with your limited resources. The theme is a medieval countryside. It can be played with 2-5; the fewer people the more strategic it becomes.
All these games are German, but a lot of better game stores are making an effort to stock German games these days. You can order this stuff online at Funagain games also, if its not available in your area.
