Great topic! I will post this here and edit later to add some good restaurants we visited during our trip.
I can definitely recommend the restaurant Khiva moon. Very tasty, friendly waiters and some vegetarian options - they can also make dishes vegetarian for you. Prices are reasonable.
We tried out the Bereddin restaurant due to recommendations and we kind of felt cheated due to the tremendous prices. We already had ordered drinks, so we decided to have the cheapest plates they offered for dinner there anyways. Payed about 15,50€ for a Greek salad, an okroshka and veg manti. Also, they sell cocktails for around 18€???
Don't go there, it's a tourist trap.