Aside from the options you've listed so far, the most obvious option is Varisian, the regional language in the area around Sandpoint. There's also Shoanti, another regional language used in the same country.
Beyond that, some of the most widely-spoken languages are:
- Draconic is used by kobolds, lizardfolk, and some spellcasters as well as dragons.
- Dwarven, Elven, and Orc come up regularly, partly because each of those races have their own countries. These are also the most common races that I've seen to not speak Common (I haven't seen any halflings or gnomes who didn't know Common).
- Sylvan is nice for speaking with fey and some plants, which are usually more open to negotiate than other creatures you encounter while adventuring.
- Aklo is a common language for monsters. That may or may not be useful, depending on how much your group favors negotiation vs. combat.
- Tien is essentially Common on the western continent of the Dragon Empires, but you're not likely to find many speakers around Sandpoint.
- Similarly, Polyglot is widely spoken on the southern continent, but not much around Sandpoint.
That said, there's a slight difference between the most widely spoken languages and the languages that you're most likely to use. Many of the creatures summoned by spells like summon monster and planar binding are celestials, demons, and elementals. While you don't need to speak to these creatures for them to help you in battle, it can be very useful (e.g., summon an air elemental to fly up and scout for you). Those languages are:
Elementals in particular often speak only their planar language.