Suggestions for Gros Morne to Lanse aux Meadows: This region of Newf is covered by the Viking Trail. The local tourism association has a good web site and publishes a free guide to just this region:
www.vikingtrail.org The road runs along or near the coast and there are many peninsulas along the way with tiny fishing villages to explore.
Two weeks is just the right amount of time. Having been there more than a dozen times, you can almost always find a place to stay without reservations. The Newfoundland Tourist Guide(
www.newfoundlandlabrador.com) includes almost all the motels, cabins, and b&bs and also a terrific free road map.
Three more things in addition to those already noted above:
1. Port aux Choix National Historic Park--halfway from Gros Morne to Lanse aux Meadows is an extraordinary Native American site.
2. Labrador: Take the hour-long ferry from St. Barbe to Labrador across the Strait of Belle Isle--reservations can be made the day you plan to go. The south coast of Labrador has a paved road, spectular scenery--especially Pt. Amour lighthouse and the Point Amour Native American burial site, ending up in Red Bay, site of an extraordinary National Historic Park dedicated to the secret Basque whaling station from the 1500s. Definately worth one overnight stay.
3. Burnt Cape Ecological Reserve--not far from Lanse aux Meadows, Burnt Cape is a gorgeous limestone peninsula with large sea caves and more than thirty varieties of rare plants, including a one site endemic and numerous arctic species. The tour guides are devoted locals and just listening to them talk is a joy.
Also: Gros Morne has some of the most spectacular day hiking and backpacking trails in Eastern North America. There are also some of the most beautiful car camping sites as well--I love the Green Point campground as you set up your tent right beside the ocean.