Oklahoma Joe's was a hit with the recent BBQ-Do.
I had lunch that weekend at Mico's (Mi Cocina) on the Plaza. Pretty okay, but not inexpensive. (glass of wine and basic combo plate $18)
Cafe Sebastien at the Kemper Art Museum is supposed to be great, but I didn't make it there. Also for more bbq, have heard BB's Lawnside is great.
Kansas City is an amazingly likeable town. At least in the spring.