I should probably add that we're a couple, both 25 years old, and have an interest in architecture, nature, good food/drink, music, photography and don't mind walking.

Several years ago in Bratislava we had a very enjoyable tour that the city itself runs. Look for the green and white "Information" sign or contact them for a schedule of their tours. Our tour was in English.

http://visit.bratislava.sk/en/

We were very taken with the charm of the main square and had our dinner there in an outdoors cafe.

I can't help you with your other travel plans, as we had a car and found the drive to Vienna very easy to do.

Most say Bratislava does not offer enough for tourists to occupy much time beyoond a half or full day.
Have you considered staying in Vienna and making Bratislava a day trip frequent train service that takes less than an hour ansd special offer tickets often for 15 euro or less round trip.

large selection of varied accomodations in Vienna .

www.wien.info

Also Dürnstein is worth a day visit -

The castle ruins just a 20 minute climb above the village- King Richard the Linohearted of Enland held there for ransom in the 1100s when returning from the Crusades.

The Churh is worth a visit witha small museum and interesting terrace views of the Danube.
Man yold buildings from 14- 15th century along the main street.

Fun to rent a bike and journey through the vineyards along the Danube.
Many places to stop for food and wine

Numerous options for a day trip look under Danube or Wachau


www.ddsg-blue-danube.at

other websites

www.wachau.at

www.duernstein.at

easytraveler: I will check out the tours, thank you very much!

molker: I have heard the same, that Bratislava can be dealt with in a day. Which is why are just staying from midday Thursday to late morning Friday. We are flying into the airport of Bratislava with Ryanair, since it was dirt cheap. So we are then heading to Vienna and have booked four nights there. It would be no point in going on a day trip from Vienna to Bratislava, when we land like 20 mins FROM Bratislava.

However, I am looking forward to the castle climb you mentioned in Dürnstein, sounds lovely.

I can understand the reason for the stay in Bratislava.
With frequent train service to Vienna you can depart almost as you wish.

train schedule available here if you do not have it.

www.oebb.at

bus service available too.

www.eurolines.at

In Dürnstein , two ways to make the quick walk to the ruins, both are marked from the village. reat views and photo opts.


Also a nice walk along the Danube- about 1 kilometer to the nearby vilae of Loiben. Some ood restaurants and wineries there too.

Just my 2 cents regarding Melk:

I was there a few weeks ago, with high expectations. And I can tell you that it exceeded my expectations. It is truly a magnificent place to visit... not sure where you read that it's overrated.

Thanks everyone, for the great suggestions! If we can find a cheap enough train, we'll go to Dürnstein at least (and Loiben).

I mentioned that I read that Krems was overrated, not Melk. I really don't know anything about either place.

Piximelle - you can read the Wachau Valley portion (Melk & Krems) of my recent trip report here:
http://www.fodors.com/community/europe/yks-trip-report-11-days-of-art-nouveau-in-vienna-budapest-spring-2009.cfm#comment-5648348

If possible visit Melk Abbey and also Dürnstein.
Above I gave a website-
www.ddsg-blue-danube.at

they offer a combi ticket for both including train trip and a boat ride on the Danube.
Both are better visits than Krems

Quite a contrast between Bratislava and Vienna.

Vienna can be overwhelming, especially as to architecture, expense and crowds. A week wouldn't cover all of it. And the best subway system in Europe helps take it all in. Pop into a Billa (grocery store) and score some of the excellent $3 bottles of Prosecco (light champagne) that are sneaking in from Venice.

Bratislava's old pedestrian section is, by contrast, cozy. You can cover the entire area in an afternoon, even with a short hike up to the castle. Cute, inexpensive cafes everywhere -- if you love beer, it's the best spot in Europe. And all just a couple of blocks from the boats that run up to Vienna four times a day in summer. There was a lovely river path along the Dunaj (Danube), but it's torn up right now for new construction.

While you might have read that Krems is overrated, it appears lovely in the photos I have seen. It certainly looks like a place that I would devote at least a couple of hours to.

http://tinyurl.com/ngcxbk

While Krems is not a bad place, with limited time, it is best spent in Melk and Dürnstein. I would not make a judgment on a place by its photos.
Living near to this area in the summer, I know a little about it.

Krems is a city of about 30000. At one time, it consisted of 3 villages Krems, Und and Stein. Thus things to see are spread out and you can spend some time to reach things of value..
If arriving by boat, the center of Krems is about 3 kilometes from the dock. You can walk 20-30 minutes, take a bus or a small sightseeing train.
The main train station is in the center.

With Melk Abbey , one of the premier sights of the Danube with its fantastic views and completely restored interior it is a must see to most everyone visitin this area.
The village of Dürnstein with castle ruins above, a beautiful Church a contrast to Melk, great terrace by the Church for good photos of the Danube, former Abbey and very nice main street - really the one and only in town making for easy sightseeing with many well maintained buildings from 14-15th century.Even a cafe with views of the castle ruins ( Cafe Schmidl ) and numerous restaurants serving good food and excelent local wines.

Seeing Melk, taking the boat down the scenic Danube to Dürnstein, then an easy train connection from Dürnstein to Krems and then with time co-ordinated train on the adjacent track back to Vienna - a full day and no real time for Krems.
In my opinion a great day

molker, when I lived in Vienna, I visited Durnstein and Melk several times but never made it to Krems. However, our dear friend was from Krems and spoke fondly of it.

As I said, I would be willing to devote a couple of hours to it just to see the old part of the town and take a few photos.

If the OP doesn't have the time, then what time she has would probably be better spent in Durnstein and Melk Abbey for they are truly wonderful.

In Bratislava, if you don't mind a short trolley ride to get down to the Danube and city center, you might save a few Euros by staying at the Hotel Turist --

http://www.turist.sk/en-hotel.html

-- which is about 3 km from the river. Bus #61 will take you from the airport to within a block of the Hotel Turist, which runs around 50 Euros/night. Bus #205, about two blocks to the south, goes directly to the city center/bus terminal (Vienna bus)/Danube, though there's tons of other trolleys and buses on the main drag (Trnavska). There's an interesting two-acre open-air Farmers/beer/flea market about three blocks to the southeast; ask about it. (Man, that .80E 0.5L 10% Topvar/Colgon beer can't be beat!)

In order to get cheap tickets till Dürnstein it is worth buying those in Bratislava. You need to purchase Slovakia-Austria Citystar ticket (Bratislava-Dürnstein-Bratislava)

At the train station you can buy a ticket for the train to Melk, includes the fee for the Melk Abbey, and the boat trip down the Danube (forget how far) and then from that point the train back to Vienna.

The Melk Abbey was beautiful. Said to be most elaborate abbey in the world. http://www.stiftmelk.at/englisch/pages_melk/TourismusEN.html

A day trip from Vienna to Bratislava would be the easiest for you as you would not be moving your luggage about.

We stayed at the Pension Suzanne in Vienna which was an ideal location. It is one block or less from the opera house, close to the metros and the shopping etc. http://www.pension-suzanne.at/english/index_2.htm