Modest budget? Your modest may not be mine. We need to know an idea of your budget. Have you looked at airfares at all. For two will probably be in the neighborhood of $2500. So where does that put your budget.
A week in Paris would be great. A week in London would be great. A week in Amsterdam, Rome, Madrid, etc.

Yes -what is your budget? The place that jumped to mind is Scotland. Not likely to be hot - but can be warm if you are lucky. Wonderful walking opportunities

London can have nice weather but can be warm/sticky. Accommodations would cost more but museums and galleries are mostly free.

Remember, many Europeans are on "Holiday" in August and some places aren't open. You would find Rome very hot in August. With the Chunnel, you might be able to divide time between London and Paris.

Well, Rome and Madrid are warmer destinations. What about Scandinavia, say Stockholm and Copenhagen? Or Germany or Austria. Norway and Switzerland are both very expensive.

It seems kind of a shame to be stuck in cities when the weather's prime for the countryside. But it depends on your interests.

When you think of Europe what comes into your mind?
What are your images of Europe?
What draws you to want to visit Europe?

These are not suggestions on where to go, but attempts to make you decide and narrow your choice.

But after all that and you want to spend money, do it in Britain; the natives are friendly and they speak the same language (sort of).

I think as long as you choose 1 place you'll be fine. It's not hard to plan a first trip when it's a single destination. Just buy a plane ticket, make a hotel reservation, get a guidebook and off you go!

Anything more north (not Italy) will be cooler... as already suggested, Amsterdam, London, or Paris would be terrific!

Switzerland's gorgous and doesn't have to break the bank if you stay in smaller towns and don't do anything extravagant. I like Vevey and Montreux (outside Geneva, on the lake) a lot.

Look into IcelandAir fares - they can have some of the lowest pond crossing pricing. You already have passports, right?

Welcome to Europe - you're gonna love it!

If you are on a budget, Switzerland and Scandinavia are pretty pricy. Since this is your first trip to Europe, I would definitely choose Paris. Paris is a beautiful city with lots to see and do and has lots of day trips into the nearby countryside. Paris can be warm in the summer but not nearly as hot as Italy, Spain and Greece. And Paris is very easy to get to.

For cooler, less expensive areas you could look at Berlin and environs, Amsterdam and Belgium or a host of places in the German or Austrian Alps (Switz is big $).

You really need to give us a budget and something abuot your interests for us to help further.

Berlin & Dresden. Take a day trip to Potsdam from Berlin.

Modest budget means hotels w/o AC so the farther north you go the better.

Or Scotland. Not likely that it will be hot in August. Stay in either Edinburgh or Glasgow and take a short escorted tour to the countryside. In Edinburgh you can hike to the top of Arthur's Seat.

Maybe combine Munich with the Salzberg/Berchtesgaden area or Munich with the Garmisch/Mittenald area.

You should check out some tours such as Trafalgar. We found them efficient - no schlepping bags, no looking for hotels and parking, most meals are included, hotels are usually very nice, they make sure you see everything, built in friends and professional guides to sites. Beware that the extra side trips can add expense to the trip.
I do like the Scotland suggestion.

A week long tour won't fit your criteria at all IMO - no time to hike and most shopping opportunities are where the tour guide gets a kickback. And just about by definition they only go to touristy areas.

However something like a few days in Edinburgh and then a 2 or 3 day tour w/ rabbies or timberbush might be a good compromise

www.rabbies.com

www.timberbush-tours.co.uk/

By modest I mean budget! For the two us us I would like to keep it under 5 thousand if possible. We speak English and Spanish if that helps. I picture walking around visiting shops, eating outside, and maybe a museum or two. I would be happier walking to most places but we are willing to drive to a side trip time willing.

So you have basically $2500 for a week after air fare (I know, maybe--but probably). So that is $300/day. Not undoable.
$100/day for a hotel. $200 for the rest, including transportation.
Choose a city (not Switzerland or Scandinavia,as mentioned) and ask. Might be possible. It WILL require being careful.
For some reason I can't go back up and correct--need probably more for room-. n
Anyway....

Doing some research (by research I mean looking at pictures) places like Paris, Vienna, and Prague interest me. i envision walking down an old street, with lots of history. Can these places be budget friendly? I would rather save money on accomodations to spend on shopping or side trips.

Paris in August is mobbed and may well be 90 degrees or more. Possible to be budget (have you looked at shared rooms in hostels?) but bigger cities tend to be more expensive.

Prague probably the lest expensive of the 3 you mention - but still you will really need to search for lodging - unless you want a room in someone's apartment.

I admit I was shocked at the airline costs. Honestly, I figured about $1000 US. Where is the best place do purchase airfare, and it it more cost effective to book air and hotel together on a website like orbitz, or separately by myself?

Go to Krakow - very cheap and you can sometimes find good airfares to Warsaw on Lot Airlines. The train connects Warsaw airport and central Warsaw and then to Krakow (3 hours).

Krakow is now one of my favorite cities. Lots of beauty and history. Very friendly people. The only thing expensive in Poland is wine and if you drink beer then you can eat and drink very cheaply.

I don't know if flights would be any cheaper, but when I read your post, Quebec popped into my head. No, not Europe but with a European feel and less hot/humid climate.
I am having trouble finding flights for close to $1000 for MAY, so I know you are struggling with August. I plug all of my potential destinations into a Kayak fare alert. I also periodically check the websites of the airlines that fly out of my closest intl airport, as sometimes a sale will appear there and not make it onto the consolidator websites. For example, Austrian Air sometimes has decent fares to some of the places mentioned in this thread.
good luck!