The pmost useful two books for starting the collection are the following:
1) Monsters & Animals. Lots of monsters, both playable and potential enemies (ranging from minor annoyance to big bad). Also, it has animal stats which are useful for pets, random encounters, familiars, and more. I'd call this one essential after the main book.
2) Dragons & Gods. It includes dragons, elementals, spirits of light, A.I., and gods. Even if none of those things appeal to you, they come in handy if someone is playing a clergy type or a warlock. Also provides a few hidden clues to the setting and such. If none if those things appeal to you though, feel free to pass. This is more likely for very high powered campaigns and/or NPC.
After those two it becomes a lot more personal taste. I'd recommend whichever location the game is going to be set. So if the Western Empire is the campaign setting, get the Western Empire book. I'll provide some added info all the same.
Old Ones: Timiro setting, and a high level campaign included.
Adventures on the High Seas: Bizantium setting. Lots of island adventures, a plethora of new O.C.C., stats on ships, and a few hidden notes (like Kingdom colors based upon nation flags). Highly recommended by me.
Wolfen Empire: Lots of Wolfen Empire info. If that's where the campaign will take place, you're playing a Wolfen, or you just like the furry humanoids, a good pick. If you prefer, you can go with the two classic [Further] Adventures in the Northern Wilderness books. Wolfen Empire is effectively those two books combined. There are definite differences, but you needn't worry about that too much just starting off.
Island at the Edge of the World: First edition adventure book. While it has setting info too, I won't recommend it for starting your collection.
Yin-Sloth Jungles: Another 1st Edition book. Lots of O.C.C. and monsters, but they'll all need to be converted. Setting info too. Good book, but due to the need conversions I don't recommend it to start off.
Western Empire: Good if this is where the campaign will be held or you want to use them as bad guys. While different, for a quick analogy I think if them like the CS. Even if you don't want to be them, still nice to have their stats when the players face them. Also has some new magic/Alchemists items, if you're into that kind of thing.
Baalgor Wastelands: Another setting book. Lots of new monsters/races. I personally really enjoy this book. However if you're not looking for new monsters/races and you're not interested in the area, it may not hold much use for a new comer to PF. I still think it's a cool book, but your mileage may vary.
Mount Nimro: Giants! A few new O.C.C., but mostly restricted to giants and that region.
Eastern Territory: Another area book. Good if you want a game there. As a G.M., it's one of my favorite places to start a game (if I'm sticking to the established setting).
Library of Bletherad: Very useful book in many ways, but also limited. They give you new schools of magic, but no way to learn them and no O.C.C. info. Rune items you can't find, etc. Also gives some setting info such as Currency and a few other gems like that. I think it's great, but more flavor and something to build/expand upon than a use as is (to me). Probably not something I'd recommend fresh out, but an early addition later. If someone is going TO the library, then essential, of course.
Northern Hinterlands: Region specific, but good book. More designed as a lead-in for the Land of the Damned though. Lots of optional O.C.C. such as Blacksmith and Artisan. Also has the Barbarians, which some people really like. Your mileage may very upon personal tastes.
Land of the Damned 1&2: Good books, but not really my type of thing. I don't use them, and actually avoid them (primarily because some of the races for it are super munchy, and after it first came out you see almost everyone trying to make one of these super ultra rare races that you never find outside this specific region, which ultimately ticked me off). High level stuff. If you're running a high powered campaign, sure. Otherwise I suggest avoiding until later. Even if you find the books interesting, not very useful for someone starting out and region specific more designed for epic level games.
Bizantium and the Northern Islands: Region specific, again. This will cover far more information on Bizantium than the High Seas book (above), and great if you want sea adventures. There's a few new O.C.C., a few new skills, and even a new type of enemy for the area.
Mysteries of Magic: I've never read much of this book myself, as my players have always avoided magic like the plague (not sure why). There are some mixed feelings on this book (from what I've seen), in part because it was meant as a series of books and the others never came out. The book does introduced new spells and various new information on magic in general. There are a few new O.C.C. (and O.C.C. variants), but can't say I've ever heard much good about them or the skills. If you want to expand on magic in general, this can be a useful addition, even for a Rifts setting. However, unless you love magic and want all the information you can have on it, this probably isn't a high priority book. From what I've seen, it tends to be often forgotten.