The Inner Sea World Guide is your best starting point to get lore on the entire region, and Inner Sea Gods is second after that to understand the religion and cosmology. But those might not be the best place to start.
Paizo has a lot of setting splatbooks for specific regions. So if you're starting in Katapesh, you would do well to start with Dark Markets - A Guide to Katapesh, for example. It's not like new PCs can just go anywhere they want without any notice, so you will get going in your campaign the most quickly by getting the couple Campaign Setting or Player Companion books about the one or two regions you plan to kick around in. Most PCs spend their entire "lives" inside one or a handful of regions, so a lot of the content in the ISWG will be interesting to you but not directly relevant to them.
Feel them out ahead of time. I'd be surprised if they didn't want to go to Abasalom as the biggest, baddest city between Katapesh and everywhere else, for example. The ISWG is great but you get a couple pages per country, if you can plan where they're going you can get the much deeper treatments of those places in time to use them in game.
Also, I'll be honest - your PCs will move around a lot less if the places they go have interesting depth and detail. Country-hopping by PCs looking for thrills generally is a result of the previous country being really boring, unless there's something specific and questy sending them on that path.
So I instead recommend the following order.
- Setting book for your starting region (e.g. Katapesh) - or, if there's an Adventure Path set in that region, the adventure path (whether you run it as an adventure or not it's chock full of setting info)
- Setting book for any specific regions you plan to go to as part of your campaign (including the planes, the planets, etc.)
- Inner Sea World Guide
- Inner Sea Gods
- Everything else
Also note that the Pathfinder Wiki has large amounts of setting information if you need to go look something up. (Don't use the old wikia one, they moved the site but wikia won't let people close down or delete defunct sites because they like the SEO and ad revenue.)