I'd recommend Pandemic. It's a little bit different to most games in that it's a co-op game, but it's a lot of fun and I feel challenges most people's perceptions on how board games should be. Stone Age is a fairly basic but fun introduction to worker placement games. Puerto Rico is fairly simple but is quite satisfying.

Basically I've found that it's good to play a variety of different board game types to see what you personally enjoy.