For the most delicious homestyle Palestinian food, Tanoreen in Bay Ridge (Brooklyn) is awesome. This is probably my favorite restaurant ever! Get their stuffed koosa (summer squash, stuffed with rice, ground lamb, and spices) with yogurt sauce! For an appetizer the eggplant napoleon is also delicious. A big meal for two will run you about $40.
For Arabic sweets, Laziza in Astoria (Queens.) Anyone here a fan of kinafeh? They have it there and when it's fresh it's delish. I think it's $4 a slice, but can't remember for sure.
For street food, Sammy's halal in Jackson Heights (Queens) is legendary. His cart is on the intersection of 73rd street and broadway. The lamb gyro with rice platter (my fave) is, I think $6. He often throws in a free soda if you're ordering more than one. He won food vendor of the year a couple of years ago at the Vendy awards.
For anyone who is a Thai food fan, you have to check out Sripraphai in Woodside (Queens.) If you love the super spicy, very authentic stuff, this is where you can get it. Dinner for two, $20-30 depending on how big your stomach is.
I really like the Afghani restaurant Bamiyan in Manhattan for their wide selection. Not sure if they use halal meat. Afghan Kebab House (several locations throughout the city) has a shorter menu but is also very, very good and I'm pretty sure they do use halal meat. Bamiyan is slightly more expensive--probably about $35-50 for two, while at Afghan Kebab House the range would be more like $20-35 depending on how much you eat.
For Belgian treats (they have a nice moules frites/mussels with french fries, as well as a terrific brunch menu with awesome waffles), La Petite Abeille has I think two or three locations in the city. I've found their location in the east twenties to be most reliable. About $20/person. Definitely not halal.
Just had some really good Pakistani food in Jersey City a couple months ago at a little hole-in-the-wall but now I can't remember the name of the place. I'll try to find out and post it when I do. They had really good pickle chicken especially.
I can vouch that Bamiyan is indeed a great Afghan restaurant. I believe the restaurant serves Halal meat, as that's what I was told the last few times I went. I recommend the mixed grill platter. They cook the meat very well, so it is still juicy & not dry & rubbery, but very flavorful as well. Location I believe was 26th & 3rd Avenue, on the corner. They even have window seats where the tables are low to the ground, so you sit on like cushions on the floor for dinner, I thought it was cool.
The paki place in Jersey City, was it Shadman?