Cactuars appear on an island, funnily enough called Cactuar Island, which is directly south of Cosmo Canyon (it does not appear on the world map, but it is there).

In regards to the sand problem, the only way you can access the desert area beyond Disc 2 is by getting a Gold Chocobo. The buggy is lost once you gain the Airship.