The only place to buy Phoenix Downs pre-palace is from the merchant Lohen in the Dalmasca Westersand. You can find him in the Western Divide area.

You can also unlock some in the Bazaar, but you'll be going out your way to do so.