The Legend 16 was listed by Dagger at 70-76 lbs depending on trim options, the wood gunwaled boat being lighter than that with synthetic rails. I owned one with synthetic rails for years and it was well over 70 lbs. I well remember carrying that beast up the 3/4 mile uphill takeout at the end of Section II, beginning of Section III of the Chattooga. Mad River Canoe also molded Legends after Dagger stopped making canoes, and there was a 15 foot Legend in Royalex that was listed at a mere 66 lbs.
The Legend 16 can be paddled solo and I did paddle mine that way some. But it is really too wide to be anywhere close to ideal for that purpose, especially if you don’t have long arms and/or a long torso. Unfortunately, the same can be said for many tandem canoes paddled solo.
The Southeast is not a bad market place to find a used boat, but if you are in the southern Appalachians as your username might suggest, many boats will possibly be more river/whitewater oriented than flat water oriented. Southeastern streams can really destroy Royalex boats through abrasion going over sharp rocks and hard ledges, so keep that in mind.
I agree with Kim that the Bell Yellowstone would be a fine choice if you can tolerate the extra weight and can find one.
One option might be to check out some paddling clubs in your area. There are lots of them in the southeast. A lot of club members will have a boat or boats that they have not paddled for years, but not taken the time and effort to list for sale.