I love board games and don't mind sitting down for 10-15 minutes with some experienced players to learn how to play a complex game. However, I don't think most of my friends are as tolerable of complexity as I am. I have a feeling they might get a little spooked at seeing a shadows over camelot board, but might be able to handle something like dominion.
What are some good games that newcomers can get started at quickly and feel proficient within a couple turns? I love games where brand new people can start developing good strategies within a few minutes.
related: How can I recognize games I should avoid buying if I only play with non-hardcore gamers?