Just down the street from the Bali Hyatt (to the right upon exiting, along the beach side), and opposite the Taman Agung Hotel is the Palay Restaurant (newly opened).

Great food (my wife had mixed grill and I had baked tuna) at more then reasonable prices.

After this meal you can shop for native goods across the street at Harvey’s Market.