James,
I wonder if we live in the same neighborhood.
I'd go with Melk for a simple reason: It's good to mix in smaller towns with big cities on a trip overseas.
If you're open to a suggestion, I have one: Consider Budapest and Melk, skipping Vienna. I visited both Budapest and Vienna on a trip to Central Europe two years ago. And while I liked Vienna, I adored Budapest. It has as much culture as Vienna, yet the pace of life isn't as crazy and the people struck me as friendlier. Of course, if your heart is set on Vienna, you cannot go wrong with that fine city.
If you do choose Budapest, one more suggestion. Visit Pecs in southern Hungary. It might be the best small town I have visited in 13 trips to Europe. Here is my review: https://community.ricksteves.com/travel-forum/trip-reports/pecs-hungary
Wear Chicago Bulls gear. Some Europeans still remember and revere Michael Jordan.
Cheers.