Europe - Need a stopover in Europe for 2 nights in May, suggestions?

I'm flying on United miles to Germany in May for a family function and have a few days to kill during which I'd like to go somewhere new.

The criteria are as follows:

No more than one connection (i.e. two flights) from the destination to Stuttgart, non-stop from Frankfurt preferred.
Someplace I've never been before (see below)
Not very expensive
Good food, interesting culture/history
Have to be able to find an award seat on a Star Alliance airline for the days in question, so several options is a plus
Having a Starwood property where I could redeem points would be nice, but certainly isn't a requirement.


I don't want to go to France, Spain (except perhaps Bilbao/San Sebastian), Italy, Prague, or the British Isles. Not anywhere in Germany either.

My initial thoughts went to either Dubrovnik, Split, or one of the Baltic states. Having never been to any of those, I could use some guidance. I'm a single guy in my mid-20s and have no problems traveling alone and getting into off-the-beaten-path or somewhat "rough" places. I don't want to spend my time lounging around by the beach or pool, I like being active and outdoors or learning about something when I travel. Metropolitan is also a plus, but again, not an absolute requirement. I'm a foodie and love weird food and the "nasty bits".

Thanks for any suggestions, I'm hoping to get this ticket booked by Sunday!

Belgrade?

Saint Petersburg?

Moscow?

Belgrade?

Saint Petersburg?

Moscow?

Can't do Russia because I don't want to get a visa. Serbia is out because my work won't let me travel there due to security concerns (unfortunately).

I should also add, I'm a beer fanatic, so maybe Belgium is a good choice?

In terms of cost, Western and Nordic Europe is expensive (take out Switzerland, Belgium, Netherlands, Denmark, Sweden, etc). I suggest Eastern Europe for prices... Budapest or Istanbul.

Poland, perhaps? WAW and KRK, among other cities, have non-stops from FRA (on LH and/or LO), and the country might interest you very much.

If you choose the Baltic States, I'm sure you'll like it there, but be warned about Estonia: it can get quite expensive in Tallinn.

Can't do Russia because I don't want to get a visa. Serbia is out because my work won't let me travel there due to security concerns (unfortunately).

I should also add, I'm a beer fanatic, so maybe Belgium is a good choice?

If you like beer, Belgium should be at the top spot :D the Delirium café in Brussels has more than 2000 different beers.

I should also add, I'm a beer fanatic, so maybe Belgium is a good choice?

I agree with WC_EEND, Brussel would be perfect in your case. (With only 2 nights, don't worry about the rest of Belgium.)
For lots of cities, 2 nights would be not enough. But it would be just right for Brussels.

And:
* it's easy to get to from Frankfurt, by air or by train.
* there are several SPG properties in the city.
* it's a paradise if you love eating (although they don't serve too many "weird food and nasty bits" :D).