I'm already planning my next vacation in next May or late August/early September. I'm planning to visit the Southeastern part of Europe. Im especially interested in Bosnia and Herzegovina, Montenegro, Albania, Macedonia, Bulgaria, Romania and Serbia. The time limit is 4 to 6 weeks. I´m interested in tips that are worth a visit, especially cities and natural sights, so that I can plan a great tour.
If hiking interests you, I'd recommend the Rhodope mountains in Bulgaria -- there are a lot of popular tourist trails between the mountain refuges. The mountain is virtually uninhabited (there are a few large-ish towns and small villages), so if you are tired of civilization, this might be something to consider.
Depending on your interests, you can choose between historical sites (such as Perperikon, which I highly recommend), natural wonders (Trigrad Gorge, Marvelous Bridges, etc.), spa centers/mineral water resorts (for example, Velingrad and its surrounds), ski resorts (e.g. Pamporovo), caves (Devil's throat) or Christian monasteries (Bachkovo Monastery).
Following most of the trails could take between 2-3 days up to a week or more, depending on your time constraints, and you'd probably still miss some places of interest. The best time to travel is from late spring to mid-summer, when the temperatures will be high enough to travel without too much equipment.
Drop a note if you need some further pointers, I'd be happy to help.
Disclaimer: Being Bulgarian, I'm obviously biased, so take this with a grain of salt.
In Montenegro: UNESCO-protected Kotor Old Town, Ostrog Monastery, Cetinje (Historical Capital), Skadar Lake. If you have enough time, it would be nice to see some mountains too: Zabljak, Durmitor, as well as Biogradska gora.
If you'd like to take part in night life than Budva is very good and while you're there, you could visit Budva Old Town. Also Maximus is located in Kotor and it is the biggest night club in Montenegro.
In Bosnia, must sees are Sarajevo (2/3 days should be enough), and Mostar (1 day).
Well I can recommend the Transylvanian mountains in Romania. Bucharest you'll likely go through (the capital) but I found it a bit dull and oppressive. Head out to Brasov in the mountains, a fantastic town, and with lots to do in the mountains all around, from Bran Castle (marketed as Dracula's castle), a mountain fortress and more. And if you're lucky, you'll see some bears as well!
In Bosnia, besides Sarajevo and Mostar, there is Pocitelj, Kravice waterall, Hutovo Blato, even Stolac (all Herzegovina is very lovely).