HamburgAround

I would recommend to try www.ltu.de. It is a major charter carrier, leaving from Orlando, Fort Myers, Miami and New York.
As they operate quite large a/c they should offer very competitive fares. They all head to DUS (Düsseldorf, a very nice city itself with one of the most beautiful historic quarter). A lot of airlines head to E Europe from there.
With LTU, there is "bid&fly"/"Biet&Flieg" in German and you may enter your accepted price and they see if it's possible; but try to be reasonable.

In the part of eating on the plane, there will not be anything to eat if you consider lccs as they not cut on this, but never introduced.

I would recommend you Prague, Budapest and Bratislava (though the center of either Prague and Budapest has become quite expensive in the past years). Krakau is a nice place to visit as well, and Zagreb too. I would neither go to Ucrania or Moldavia, but that's just my thought.

Don't forget to visit Warsaw, a very beautiful city and the capital of Poland. Tirana and Albania in general is very beautiful as well.

centralwings is a lcc to Poland. But riding the train is cheaper and a very nice thing to meet local people. There are night-trains guarded and therefore quite secure for a nights rest.

Justme123456

I, too, highly recommend staying in Prague. I was there about a year ago and was astounded how little I spent on really good food and some of the best beer in the world. I recall a decent draft beer at a nice bar for costing about 30 CZ Koruny, which was just about $1USD at the time. It's a great city, to boot!