I would say that southern Poland would fit your criteria quite nicely. The southern area of what is now Poland has been at the "crossroads of empires" since the middle ages, between the Kingdom of Poland, the Holy Roman Empire, Hapsburg Austria, the Bohemian Kingdom, Prussia, and the Russian Empire, which gives this area quite a deep and rich history.
Even though it is in the heart of Europe, I would say that southern Poland (save for Kraków) is definitely off the international tourist radar. The best way to see this land would be from a car. One could take the 4 hr bus from Prague to Wrocław, in the south western corner, rent a car, and then work one's way eastward and fly out of Kraków.
For potential sites:
Wrocław - the historic capital of the lower Silesia region, in 2016, the city was named a European Capital of Culture and is home to Centennial Hall which is a UNESCO World Heritage Site. The old center is quite unique, as it incorporates a little of every country that has ruled the city - from Silesian Gothic to Austrian Baroque and German Modernist.
Sudeten Mountains - a forested mountain range along the border between Poland, Czechia, and Germany. The Sudetes were mostly spared from the horrors of WWII, as most of the fighting went north, so many of the small historical German spa towns and related sites are well preserved.
Zamek Książ - (Schloss Fürstenstein) a large, originally medieval castle of the Duchy of Pleß, that overlooks the Pełcznica river gorge. During WW2 the Germans built underground tunnels here. In these tunnels is apparently where the train filled with Nazi gold is hidden. This tunnel network was part of Project Riese, which was a secret Nazi project consisting of several underground megastructures (for yet unknown reasons).
Protestant Churches of Peace in Jawor and Świdnica - UNESCO World Heritage Sites, the largest timber-framed religious buildings in Europe, built after the 30 Years War, when this area was part of the Austrian Empire.
Schloss Pleß at Pszczyna - Baroque style chateau, which used to be owned by the von Pleß family. The interior is very well preserved and many of the original stuff are all still there. It is also historically important as this is the place where Kaiser Wilhelm II had his HQ for the eastern front during WW1.
Katowice - largest city in the Upper Silesia historic region, a vibrant center of Silesian culture. Its modern architecture contrasts its architecture from the early 1900s, historic reminders of Katowice's German and Communist past. Especially nice to visit in April with its numerous flowering lilac trees.
Kraków - The former royal capital of Poland, with its historic center designated a UNESCO World Heritage Site, Kraków is a historical and visual gem. Its home to one of the most magnificent (and largest) squares in Europe. The lively squares and backstreets of the former Jewish quarter, Kazimierz, symbolizes the dynamic renewal of the city.
These are just some of the larger sites one can see, there are still many smaller, yet equally interesting, places waiting to be discovered. The best part - everything is dirt cheap, I mean the water is more expensive than the beer over there. Throughout the region, you will find some petty good Polish Pilsner and authentic medieval honey-mead.