jjwdiver:Guidos is high on the list, but maybe something different. I went to a place a couple blocks off the waterline that you enter from the front, walk through the indoor seating area to a courtyard. Great seafood platter! Cant for the life of me remember where it was or the name of the place. Just a couple blocks at the most from the Yukatech shop.
Sounds like La Veranda to me, too, but it's in the first block from the water and north of the Plaza, and not far from the Cinco Soles shop. I really like that place; it's a bit classier than most of the Coz eateries, not that there is anything at all wrong with the others, but it's romantic, with a fountain and a gazebo, soft lights and music.