I'll add my two pence by weighing in on the side of additional possibilities for the periphery of Gondor.
In a nutshell, look what C7 are doing with the people and places in Middle-earth that Tolkien didn't develop in greater depth, such as the Vales of Anduin/Mirkwood points already raised. Heck, they've already compiled entire books (
DoM, etc.) on the subject, with tons of flavor and adventure.
Concerning Gondor, we have the border realms such as Ithilien and fighting the rise of the Shadow to the East, as well as the Southern Fiefs.
So C7's progress with Rhovanion inspired me to take another look at one of my favorite stories - the Long Winter. Three Corsair fleets ravaged the areas around the Lefnui and Isen Rivers, while the Dunlendings and Easterlings further invaded Rohan, and it was a time of turmoil and fear. The Free-peoples rallied and defeated the invaders, however, there is a gap in Tolkien's lexicon (as it were) about the people of that area in the time leading up to the War of the Ring. We have some great tidbits, such as the march of the outcompanies to defend Minas Tirith, as well as a few other references, but not much.
Thus, I'm writing a chronicle that starts the companions in that area and am converting adventures from
TOR, D&D (gasp), et al: they'll tangle with everything from Corsairs, to smugglers, to Orcs from Isengard (and the whole can of worms that opens up about revealing Saruman
), to the Dark Men of the Mountains, and perhaps even a Corsair shipwreck where the dead do not rest easily...
To summarize, they'll battle to halt the spread of the Shadow in the true vein of Middle-earth, while simultaneously venturing into uncharted waters, as it were (they may even head south).