Once you have a seafaring vehicle, you are free to explore any of the four Continents, and you will be able to reach landmarks which will increase your Stats. The Continents are virtually identical, and the recommended order is simply based on the difficulty of the monster each Gem-bearing king will send you to kill. To that end, the most logical destination is the Lands of the Feudal Lords, which is east of the Lands of Lord British. The eight towns here are identical to those you've already seen in all but name, so don't expect any surprises. The two castles are also quite similar. You'll find the The Castle Rondorin on the eastern side of the continent, on the inner sea. This king will instruct you to kill a Carrion creeper, which can be found on Dungeon Levels 5–6 of any dungeon. You may want to return to the dungeon where you finished your first gem quest, if you mapped it out, or you can visit a more local dungeon. Upon completing your quest and returning, the king will reward you with the Green Gem. He will tell you that you need to use the Time Machine to win, which you will likely already know.
Aside from the main quest, there isn't much interesting about the Lands of the Feudal Lords. You'll find new landmarks, and the king in the The Castle Barataria will send you to the The Southern Sign Post for his quest. Since this landmark is in the next continent you're likely to visit, the Lands of the Dark Unknown, it is worthwhile to begin the quest before leaving.