S'Agapo: 34-21 34 Ave.  Greek and my personal favourite in South Astoria.  Very friendly,  nice terrace, and can always get a table.  Best for meat  - excellent steaks and grilled lamb, but also a really nice red mullet treatment, and unusual appetizer dips.
 

Aliada. 29-19 Broadway. Astoria, Queens 718.932.2240 On the West side of 31 St.  Greek and my recent South Astoria favourite.  Here is Asimov's review:

One distinguishing feature of Greek Cypriot cooking is the use of cilantro. Native to the Mediterranean area, this odiferous botanical was once a cornerstone of ancient Hellenic cooking and preserving. Since then it has meandered around the world, so that now Mexican, Chinese, and Indian food are unthinkable without it. Nevertheless, modern Greek cuisine virtually ignores it. Yet the stinky herb is a prominent component of Aliada's horiatiki salad (large $8.50, larger $10.50), a lush tangle of cucumbers, caper leaves, arugula, scallions, lettuce, black olives, feta, and tomatoes. As with the other eight salads on the menu, it arrives intentionally underdressed, encouraging you to pour on the olive oil and red-wine vinegar with a free hand. Cilantro also makes a stunning appearance in keftedes, oniony Cypriot meatballs so light they threaten to fly up from their green lettuce bed like well-driven golf balls. Eight to a plate ($7.95), they arrive blackened all over from a final charcoal grilling.
A scant 60 miles from Syria in the far eastern Mediterranean, and far closer to Turkey than to Greece, Cyprus was riven by a 1974 conflict, so that now the top half is Turkish and the bottom half Greek-ish. Located in remote northern Astoria, Aliada revels in the food of the Greek half. Like most Astorian restaurants, the kitchen chugs along in the front window as a lure to passersby, and the dining room looks like any other modern dining room in town, with exposed brick and whitewashed walls, save for a niche toward the rear that holds a hookah, a ceramic olive-oil jar, and a gigantic flask of Metaxa, a brandy, with a brass spigot near the bottom of the bottle for quick access. Indeed, the Cypriot wines at Aliada are particularly impressive, including Keo Othello ($24), a dry, light, fruity red, and Commandaria, a sherry-style digestif named after an order of knight. Have a glass with the wonderful dessert of yogurt, nuts, and golden Greek honey ($3).

It will come as no surprise that a number of Middle Eastern specialties have crept into the Cypriot table of mezedes. At Aliada, you'll find a fascinating hummus ($4.95), looser and more chunky than the usual chickpea puree, and a version of tabbouleh too. More surprising, perhaps, is the falafel. Shaped like small footballs, and larger than average, these falafel have a rugged texture and a distinctively nutty and cinnamony taste. They clearly do not come from a box. You could easily make a complete meal of the vegetarian mezedes, and if you do, it should also include manitaria krasata (mushrooms cooked in wine), kolokithokeftedes (free-form zucchini croquettes), kopanisti (a Slavic-seeming mush of red pepper and feta), and especially, the charcoal-grilled haloumi cheese in all its charred and rubbery glory. Like Texans, the Cypriots will grill almost anything.

Though the menu neglects seafood, there is a fine grilled-octopus appetizer ($11.95). But this cephalopod makes more of an impression in a salad named after the restaurant that matches the tentacles with potatoes and strips of roasted red pepper. All this is leading up to the best thing on the menu, charcoal-grilled lamb chops ($19.95). Five to a serving and accompanied by a fine plate of fries, these luscious chops have no equal in Astoria-perhaps in the entire city.
 

Butcher Bros. 29-33 Newtown Av. Steak, (29/30 Sts.), Queens, NY (718) 267-2771. (next to Amici Amore Italian rest).  Very good steaks -
including a superb veal chop.  Good wine list.  The restaurant is really part of Amice Amore, and you can get all the steaks in the Italian side, and can also mix and match menus (which is what I do).

Cavo: 42 18 31st St . Latin, with huge and dramatic interior courtyard/terrace  and interesting Latino noveau cuisine.  Great in summer in company.

Brick Cafe. 3095 33rd St. Astoria, NY 11102 (718) 267-2735. Cross Street: 31st Avenue.  This is a rare find - a non-Greek, but reasonably up-market restaurant and cafe, that makes a pleasant change when you are maxed out on Hellenic.    Has pavement tables, with overhead heating in fall, which makes it a very pleasant place to sit out at.

La Portena:  74-25 37th Avenue, Queens 718-458-8111. Brazilian and good for perfectly grilled entraña (skirt steak) and  blood sausage.

And finally, here are some I haven't been to, but which got good reviews, and which I will visit in the fullness of time.

Zenon: 34-10 31st ave. Greek, good for casual dining and meze

Praha:  28-48 31st St. Not been, but eastern European, so hearty and best for winter.

Cup Diner & Bar.  36-2 35 Ave.  Astoria, NY 11106.  718-937-2322.  Not been but this diner has been recommended in a few places.

Cafe Bar. 32-90 36 Ave. Astoria, NY 11106. 718-204-5273. 

Le Sans Souci - French, 4409 Broadway (44/45 Sts.), Queens, NY (718) 728-2733.  French bistro in Astoria with European décor, a Mediterranean influenced menu and sidewalk dining. $$.  I have not been, but here is the NYT review:

Le Sans Souci pays homage to a bistro
you might find in a working-class hamlet in northern
France, with stone walls, wide-plank wood floors, and
shaded sconces. Its kitchen turns out simple cuisine
grand-mère, like moist slices of pork loin braised in
Calvados, or scallops in a rich lobster and saffron stock
thickened with puréed tomato, and it serves hard cider from
Normandy the French way, in broad porcelain cups.

The place comes by it honestly. Jean-Pierre Le Pape, who
opened Le Sans Souci with his wife, Stephanie, an Astoria
native, moved to Queens in 1982 from Lorient, a town on the
south coast of Brittany. A decorative painter by trade, Mr.
Le Pape designed the interior, and painted the
trompe-l'oeil pastoral scenes set into faux arched windows
in the walls.

"I wanted to have a place where you could feel with all
five senses like you're in France," he told us. Diversity,
he said, is Astoria's greatest asset, and though there are
few Bretons in the neighborhood, he noted that the
residents of his block include Irish, Italians, Thais,
Japanese, Greeks and Croats. "I want all my customers to
feel at home," he added. "Nothing stuck-up."