We visited Martha's Vineyard for the first time this July, and were impressed with how much beautiful shoreline there is, and places to bike/hike. It sure has the history aspect covered, too. We stayed at the Harborside Inn in Edgartown, which housing is in whaling captain's mansions. Very nice. We also had a direct view of the harbor.

We did not have a car, and were glad of it. The bus system is sufficient, frequent and inexpensive. We took it one day to Oak Bluffs and back. Another day to Aquinnah to see the beautiful beaches and cliffs.

One afternoon we rented bikes and rode all over, including to South Beach. The Winnetu Resort is there. We had considered staying at Winnetu, but were glad we didn't, because it is rather remote and did not look like much.

Bike paths are conveniently located, so we did not have to share the narrow roads with cars too much. Although drivers seemed to be very observant of bikers and were polite about giving us space.

Chappaquiddick island is a short ferry ride from Edgartown. It is a nature preserve where you can hike to your heart's content. Vehicles are not useful there. We did a nature kayak tour of the Cape Poge Wildlife Refuge. They picked us up at the ferry, and we chose from single or double kayaks. Our guide was a young high school student, who was so enthusiastic and fun. He took us through the salt marsh and told us all about the birds, the wildlife, and the vegetation. He even dove into the water and found different things to show us, like a jellyfish, and snail-like creatures we could eat. The tour was supposed to be 2.5 hours, but he spent about 3.5 hours with us. We highly recommend going to this refuge, which also offers tours by truck and has a Japanese garden for walking, called MyToi (pronounced 'my toy').

You can take a Mad Max sunset sail, which leaves at 6 p.m. for a two hour cruise. You can bring onboard any food and drink you want, which I recommend you take a picnic dinner with you.

East Coast. Late May or early June.
Hiking. History. "small beaches or coastal views."
Hmmmm.

My first thought was Cape Cod, but then I noticed when you were going. That area has all of that, but can be quite cool until later in the summer. If you don't mind a stiff, cold breeze on the beach, and water WAY too cold to get in, it may still suffice. These pdf's may help you:
www.nps.gov/caco/planyourvisit/upload/2009selfguidingrevise.pdf
www.nps.gov/caco/planyourvisit/upload/Scenicrevisefinal-2.pdf

To get a little more warmth, you'll have to go further south.
Savannah and nearby Tybee Island may be exactly what you're looking for. Not GREAT hiking, but a lot of history and TONS of charm and romance. If it's the latter you REALLY want, then Savannah can NOT be beat.

Or possibly the Outer Banks if you're looking for a little more seclusion. Less history than Savannah, but better beaches and hiking.

thank you both! We know it will be too cold to get in the water...he loves to just sit and watch the waves and listen to the amazing sounds. I will check out both of your recommendations and appreciate your time in writing

Take a look at the Cape Cod National Seashore and those towns. There are plenty of walks, though not hilly hikes. And also, even though it will be colder, I would recommend looking also at the Maine coast--Ogunquit, Camden, etc. There you can more easily combine hikes and seacoast views.

You might consider the Litchfield County area inc. the towns of New Milford, Bridgewater, Southbury, Woodbury, New Preston, Washington, Warren and Kent and Kent Falls. Places to walk, but no waves except in Lake Waramaug. Lotsa antiques too.

If you are on the CT coast, there are nice hikes to be had at Bluff Point State Park and Hammonasset State Park.

Nice historic homes in Stonington, CT.

Acadia National Park in Maine
http://www.nps.gov/acad/index.htm

late May/early June could be black fly season in New England woods. Depends on how wet/cold spring is. I think we had bug free weather around June 12 in Ogunquit last year. From Camden north to Bar Harbor, I would consider timing a visit to coincide with lupine bloom/festivals (Stonington ME area).

As much as I love Cape Cod and Acadia National Park, the Cape and islands are not the first place I think of when I hear the word "hiking"; nor does Acadia usually spring to mind when I hear the word "history."

In my opinion, the absolute best of both worlds can be found in the Lakes Region of New Hampshire. You have extremely picturesque historical towns like Wolfeboro and Sandwich nestled between the lakes and the mountains. There's tons of hiking in the Ossipee and Sandwich Ranges, with the awe-inspiring White Mountains a short drive away.

If sitting by the edge of the lakes doesn't quite cut it, the seacoast is only a short drive away; Portsmouth, NH is one of the most beautiful and historical coastal towns in New England. I very highly recommend it. And from Portsmouth, you can easily hop down to the ultra-historic North Shore of Massachusetts, including Newburyport, Ipswich, Rockport, Salem, etc.

The only other area that I think combines hiking, history, and water so well is the mid-coast of Maine, specifically Camden. You've got the Camden Hills which offer some fantastic hiking with amazing views and all of the towns along the coast (Wiscasset, Damariscotta, etc.) are very historic. While you don't have the variety and the challenge of hiking options in the White Mountains, you could seek out more high terrain in Acadia National Park.

For these reasons I would suggest going north from Boston rather than south, via MA's North Shore, Portsmouth, NH's Lakes Region & White Mountains, and possibly the Mid-Coast of Maine if you have the time. It is true, however, that you may encounter some annoying black flies during your hikes... you might want to bring a strong insect repellent.

The other area where you can combine the outdoors with some history is the coast of Lake Champlain in Vermont. There is a surprisingly rich maritime history in the area, plus several museums. You can easily drive across to New York to visit the forts (Crown Point, Ticonderoga) Plus you have the nearby Green Mountains for hiking.

I also second the suggestion of Portsmouth. Plenty of seacoast scenery nearby, plus the historic homes in downtown Portsmouth (check out Strawberry Banke).

Mid Maine (Camden); you have hiking, ocean, quaint historic towns, awesome seafood, lots of history everywhere, wonderful photography, amazing sights. I think it will fit the bill and give you everything you both love.

thanks so much for all your responses. TerrMys, you may have pegged me to the tee! What an insightful response. I will take what all of you have said and do as much research as possible. thanks also for the warning about black flies, we're not use to those in St. Louis.

Don't know if you've made your choice already or not, but an added suggestion might be Philadelphia and surrounding areas. Won't work if you want your history, hiking and water all in one spot, without getting into your car. Nor would it work if you only want mountin hiking. But if you don't mind driving an hour or so for the hiking or a couple hrs. for the water, then there are many lovely spots. If this is of interest to you, I'd be happy to get more specific...seems silly to do so, if this wouldn't be up your alley.

I highly recommend Mount Desert Island and Acadia National Park in Maine. MDI is an island the size of Martha's Vineyard -- with 24 mountain peaks. So, you get iconic Maine rocky beaches, the Bass Harbor Lighthouse, and lobster pounds...along with 130 miles of pristine hiking trails. The island is full of history, from the Abbe Museum devoted to the Wabanaki Indians to John D. Rockefeller, Jr. and the early rusticators, especially George Dorr, who turned so much of their wealth into its preservation. I think you and your husband will love it. Check out www.ouracadia.com (and particularly the blogs about hiking trails) to get a better feel.

Nobody knows NH like dhfrostnh.

Please listen to what she says.

NH, Maine, and Vermont are all subject to black flies at this season. Not guaranteed to have, but subject to.

Look at the hunting and fishing pages at LL Bean to see how locals cope: hats with built in netting, clothes saturated in repellents.

Think coastal, think southern Maine, think Cape Cod, think Nantucket, think (shudder) the Vineyard. No, only joking.

Have you read Thoreau's Cape Cod? You might try taking some of the routes he described to see what the area is like 175 years later.

If you don't come until July, all the recommendations above are good, and you can even hike some of the more accessible areas of the Appalachian Trail or hike up Mount Washington.

If you decide to stay on the outer Cape you will find plenty of places to walk, especially in the National Seashore. Since the outer cape was the original landing place of the "Pilgrims" you will find historical locations all over the place, from Corn Hill in Truro to First Encounter Beach in Eastham. Here are a few suggestions for trails to consider
http://navigationshilfe.t-online.de/dtag/dns/results

oops, don't know where that last link came from ....let's try it again!
http://www.trails.com/activity.aspx?area=14651

I'd make it a two-part vacation. You could spend a few days in Boston getting your history fix ... even consider a day trip from Boston to historic Salem (it has a rich maritime history as well as the tragic history of the witch trials). Then rent a car and head to Cape Cod for some nice nature walks and seaside relaxation.

I live in NH and hiking here tremendous in the White Mountains. But, do you mean hiking as in walking trails or hiking as in mountain hiking? Here is the link for the White Mountain National Forest in NH. It includes the majestic Mount Washington peak (you don't have to hike it. It's amazing just to see from a distance).

http://www.fs.fed.us/r9/forests/white_mountain/

Late May/early June in Savannah will be really warm. Really. It's beautiful though. If you decide on Savannah, I'd consider late March or early April. The azaleas will be in full bloom.

Any thought to the Appalachian Trail? I just finished a book "A Walk in the Woods" by Bill Bryson about his hiking many miles on the AP. You would enjoy the book even if not following in his footsteps.