Echoing Damien's sentiments, all of the supplements I've purchased thus far are among the best (if not THE best) in the market today. Really, I would tailor your selection/order of acquisition based upon the kind of campaign you and your players want.
Road of Kings - as a long-time Conan fan maybe you won't need this. For myself, this book was invaluable for really understanding the cultural differences among the peoples/nations.
Pirate Isles - hands down, best pirate-seafaring sourcebook I've seen. In a trend that continues through all of the supplements, this isn't your typical d20 sourcebook of prestige classes, feats, and spells. Oh they're still there, but so is a lot of Hyborian fluff, sample NPCs, new mechanics that address the topic of the book, etc.
Free Companies - want Pirate Isles does for pirates, this book does for warfare. This gives you the tools to run a campaign that seamlessly blends war and military aspects into the game. It's also a mature treatment of the subject matter rather than the sanitized versions you typically see (esp. from WotC).
Hyboria's Fiercest - worth buying just for the guidelines on effectively multi-classing to achieve fantasy archetypes without resorting to new core or prestige classes. Primarily a "crunch" book, this book is far above the standard d20 class-themed splat book. I'm eagerly awaiting the next two books: Hyboria's Finest (Soldiers, Nobles, Scholars) and Hyboria's Fallen (Thieves, Pirates).
Scrolls of Skelos - If PC scholars (as in multiples) will be present or if NPC enemy sorcerors are going to comprise a significant portion of your game, you might want to pick this up. Expands the sorcerous options presented in the core rulebook. Also has a good beastiary section for otherwordly wierdness.
Aquilonia - Regional sourcebook. Detailed treatment providing a gazeteer of the kingdom during Conan's reign. Sample NPCs. Writeups of King Conan, the royal family and key advisors. Also, what classes are popular (or aren't) and why.
I plan to pick up Hyboria's Finest and Across Thunder River next. The cities are on my list, but I haven't got around to them yet.
Azgulor