I have never been to Budapest, Vienna, Krakow, but understand all are beautiful. I have been to Prague twice and think it is one of the world's most beautiful cities because very little has been destroyed from the 13th Century onwards. I certainly would advise against attempting to see all four of these wonderful cities in a week. You will be able to say you were there, but will be unable to say you really saw much. If you are into nature, Prague has two castles, Prague Castle, which is magnificent and which everyone goes to (it is the largest castle in the world). However, the other castle, Vyšehrad, is more like a park than a castle and is rarely crowded. Also, Petrin Tower and park overlooking the city is wonderful.
Finally, even if you don't enjoy music you should opt to buy some inexpensive tickets to a string quartet or other event (or even spend a little more for symphony or opera tickets). Prague was Mozart's second home and listening to music is a must, in some of the most beautiful venues you have ever seen.
I'd agree with Scott down there. As much as I adore Krakow (never been to Budapest), it does make more sense to go to Vienna and Prague given the proximity. Both cities are absolutely fantastic. And the idea of stopping in Cesky Krumlov is also solid. It's like a Disney movie come to life there (with much better beer). In fact, I'd almost recommend a couple days there for the full experience. I might also add that there are car services based in Cesky Krumlov that will pick you up or take you to any of those three cities for prices very competitive (or even better) than the train. It's a much more relaxed form of travel. When we took a car service from Vienna to Cesky Krumlov (and then later on to Hallstatt and Salzburg), we also stopped an hour along the way for lunch in Ceske Budejovice to have the original Budweiser beer next to the brewery. Hope you enjoy your travels!
Take your time in Prague and Cesky Krumlov. It's easy to get around in Prague by foot or tram. Even if you're not tourist types, you should enjoy the beauty of the Czech Republic.
With losing a day due to the change in time zones and having a travel day at each end, you're really only looking at 9 days. Add another 2 or 3 travel days jumping around and....you're not going to enjoy your holidays much.
I'd pick TWO of those cities and spend 4 days in each with a day to get between them.
I can also recommend spending a night or two in Cesky Krumlov. Halfway between these cities, it just makes sense.
This 14th century 'untouched' village is my now my home. Come visit!!
Where you will begin and end the trip really depends on your available flights. As round-trip air tickets are much cheaper than one-way or open-jaw tickets it makes sense to plan a round-trip.
In Europe the best way to get from place to place is by train. Trains are safe, easy to use, comfortable and reasonably-priced. All the places you mention are linked by train, with regular services. In the Czech Republic, Hungary and Poland fares are very reasonable indeed.
For train information do not use ticket-agency websites such as Raileurope or Eurail. They do not list all departures and charge admin fees.
For times and details of almost all European trains in English (no fares other than for and from Germany) look at the official German railway website:
The official railway sites for the other countries have English versions and usually give fares as well as times and details. If they don't you can be certain that the fare is very reasonable indeed.
Czech Republic http://old.cd.cz/en/
Trains do not *have* to be booked in advance online ...indeed, most cannot.
You have 11 days altogether. Checking-out of your accommodation, travelling, orienting yourself, finding and checking-into your new accommodation will take up most of one day. You also have two flight days so, if you plan to visit four places, you will actually only have 6 full days to explore.
With only 6 full days, and because you are seeking a 'relaxed' trip, I'd suggest you cut out one of the cities. Either visit Prague, Vienna and Budapest or Prague, Krakow and Budapest. The order you visit can be determined by your flights.
All the cities I've mentioned are fascinating, stuffed with history and things to see and do. All have lovely parks but none have much of 'nature' because..well...they're cities! If you wish, you can easily make a daytrip to Bratislava in Slovakia by boat or train from Vienna....or a daytrip from Krakow to Zakopane...or a daytrip by boat from Budapest to Szentendre...
Enjoy your planning! :-)
Taking in too mucha at a time dims savoring
Just two cities developing tours in areas around the cities (prague and krakow) is a better travel exp.