Try Prague (my first choice) or Budapest, or both (taking a train between). They are not yet on the Euro; however, they are also not as inexpensive as they used to be. English is widespread (at least in the tourist areas) and there are many sites/sights to see and much to do. They are both very interesting places (take a tour of the Jewish Quarter in Prague, highly recommended).

Edited to add: Darn, hhonorman beat me to it.