Yep, that was my thought exactly — start on Numenor with the capture of Sauron and the corruption of men. It would have the dark feel and rich storyline that made GoT so popular. You could see the first two seasons take you through the Last Alliance.
Tell this story for example,
King Elessar now ruled [in] all the lands of those realms of old he was king, save in Rohan only; for he renewed to Éomer the gift of Cirion, and Éomer took again the Oath of Eorl. Often he fulfilled it. For though Sauron had passed, the hatreds and evils that he bred had not died, and the King of the West had many enemies to subdue before the White Tree could grow in peace.