Perkins Notch is a great place to stay - there's a lean-to shelter plus plenty of nice open area for tent setups, as well as abundant water. It's a very mellow hike in from either Wild River Campground or the end of Carter Notch Road. I'd recommend late in the summer, though, as it's a very buggy area and the approach can be muddy, too. The best day hike option from there goes right up the Rainbow Trail to Carter Dome.
Heck, you could camp right at Wild River Campground (primitive but car-accessible; no reservations) and do some fantastic day hikes, ranging from Moriah on one side to the Baldfaces via Eagle Crag on the other. Do check to be sure Spider Bridge has been repaired if that's on your route.
Another option I'm surprised nobody mentioned is Thirteen Falls tentsite, down below Galehead in the Pemi Wilderness. There's water, swimming holes, cascades, plenty of tent platforms ... that spot makes for a fine base camp for heading up to the Twins, Garfield, Galehead, or around to Owl's Head.
And finally, yes, there are some wonderful backcountry sites in the Gulf. They all have water very closely nearby in the form of a river or brook, and none have any privies. They're just hardened little clearings and are marked with little tent signs. No fires allowed. Any hike from in there is going to be a solid workout. Well, actually, the Buttress Trail up to Madison Hut wasn't that bad, and does get above treeline into views fairly quickly.