Choosing games for a group with wildly different experience levels

Our game night has a player who knows every strategy game on the shelf and another who has barely played anything beyond party games. If we choose something deep, the newcomer is overwhelmed; choose something too light, and the veterans drift away. I've had better luck with games that offer interesting choices but few rules exceptions. What titles create real decisions without rewarding years of genre-specific knowledge quite so heavily?