Alright, since we did almost nothing on the NC side, I guess my input really isn't applicable. But I'll give what I know anyway, in case you spend any time on the TN side.
Cosby - for the first few days we camped here, and it was our favorite campground. It's really separated from the main park entrances. You can only reach a little corner of the park from here, and it's about 20-30 minute drive to any of the other entrances which take you to more "touristy" areas. But it basically never fills up, nice and woodsy, and was the least "busy" campground. Cosby Creek was also within walking distance, and fished better than anything else I fished all week. It's a smaller creek and had a combination of wild bows and brookies.
Elkmont - I passed through but we did not stay here. It looked nice, is in a nice woodsy area and well located to give you access to virtually anywhere you want to go. Plus its on the Little River in trouty territory, I walked up and fished one day, caught a few, but the stream was beautiful and I wish I had the time to walk miles up. Mostly bows, and I did catch a nice brown. But in July, the campground was PACKED, this is definitely the most in-demand campground.
Townsend - we stayed on a private campground right against the river in town. Townsend was nice, more laid back and not so touristy like Gatlinburg. Everything you could need in town. The campground was just a little yard to throw a tent up in, good enough but not what you're looking for in a tenting experience. I did catch a few smallies and 1 stocker rainbow right at the campsite in town. In hindsight, I wish we'd have stayed at the small campground at the lower end of Abrams Creek.
Streams:
Cosby Creek - fished the best for me. Runs by the Cosby campground, smallish stream, mixed brookies and bows. You'd have 100 yard stretch with all brookies, then the next 100 yards would be all bows, and back and forth.
Little River - stocked in the town of Townsend. Smallies fading to trout at you go up. Elkmont and above is prime trout territory. It didn't fish so well the day I fished it but it looked like a nice stream and the fish were there, I caught less than 10 in 5 or 6 hrs, though.
Middle Prong - I fished the upper end, before it split into Lynn Camp and Thunderhead Prong. It fished very well, all bows. I didn't have that long to fish it, though. At the top there, where it split into prongs, there were waterfalls on both branches, and above the falls both branches were closed to fishing. They were poisoning the bows and trying to establish brookies, I think.
Roaring Fork - I just screwed around here for an hour or so, on the downward side of the Roaring Fork Motor Trail right out of Gatlinburg. In an hour, I caught double digits, so it fished well. Smallish bows. Very scenic area, but lots of tourists.
That's all I fished, as it was a family trip, not a fishing trip. I never did hit Abrams, which is the famous one, a limestoner. I hiked along it from Cade's Cove down to the falls. Saw some fish. Slower and bigger and very touristy. Probably fishes more like a limestoner, with pickier fish.
I think virtually any stream in the park is gonna have rainbows, on either side. I wanted to fish some of the higher country, but never got the chance. For instance, Road Prong was high on my list to try. But I only fished while the wife did some short hikes, and she was 5-6 months pregnant, and thought the terrain up there was too dangerous for her and the baby.
Fly Shops:
The only one I visited was Little River Outfitters in Townsend. But I was very impressed, excellent fly shop.
