If you don't see Foothills on the World Map, try progressing further in the game. Foothills may become available later on.