Another vote for Lotus of Siam. Absolutely killer Thai food, unlike anything I’ve tried. Don’t forget to try the sticky rice and coconut ice cream for dessert.
Another great place that locals and hopefully more tourists discover is Rosemary’s. It’s on Sahara, but a ways away from the strip. It’s a little place in a strip mall, but it’s probably my favorite restaurant in any city.
The service and the food is so stellar and unique that it is really a must-try for anyone who enjoys going to restaurants. Everything I’ve tried from there is amazingly good, nice sized portions and a thoughtful beer and wine list.
Also, if you do want to try a higher end place, check out Thomas Keller’s restaurant in The Venetian. It was one of the 10 best meals I’ve ever had, and I’m both a foodie and a cook.