I really liked all, or at least most, of the frame narratives discussed in the 'cast. I probably am leaning most towards a young Aragorn as the main frame. The reason why is because I prefer a frame to have some dramatic tension in it, and for the stories that are to be told to have some real consequence for the frame. So while I do like a post-LOTR Sam, there don't seem to be many situations that would really create that level of tension for him or his kids. On the other hand, watching Aragorn grow up and people trying to impart these stories to him because he is essentially the last "hope" for Middle-earth could be really engaging. We could learn that the person he grows to be was influenced by the lessons he learned from these stories. This also gives the opportunity for multiple story-tellers, each with a unique connection to the particular story.
Gilraen with Beren/Luthien would be great. I like the idea of her telling Aragorn the story as a cautionary tale of why Human/Elf relationships don't work out and then Aragorn ends up drawing a completely opposite conclusion. Oops. Elrond telling him about his dad (Earendil's) journey would certainly be fitting. Etc. Anyway, this is my vote, but I'm certainly open to others.
I'll put one more candidate out there, though, for discussion's sake, that I haven't heard mentioned:
What if our frame is in the Second Age, in Numenor itself right before the fall? The main characters would be Isildur, Elendil, and Anarion, and our story begins as Sauron is gaining influence and some of the Faithful start coming under his influence. What if the stories are told by Elendil, and perhaps we can even have some Elvish visitors to Numenor to tell these stories as well, and he is using them to explain to his sons what is happening and why they must remain faithful. Perhaps we can even take some dramatic license and say that Isildur and/or Anarion are partially intrigued by what Sauron is saying, and they must be shown the truth. The advantage is that this narrative frame would have a ton of tension, and there would be a lot you could do in the frame itself. The disadvantage would be that a lot would have to be explained in the frame itself, and we'd eventually have to move past its time frame if we wanted to tell further Second Age stories, but you could have the seasons advance the story towards the Battle of the Last Alliance. Imagine the first episode of the first season showing Sauron being brought to Numenor. Chills!