While this question was asked for the original version, this answer for both the original version and Zodiac Age version.
In the original version, as Nickle states, the earliest point in the game you can get an Embroidered Tippet would be stealing them from Coeurls in either the Golmore Jungle or Tchita Uplands with a 3% drop rate. However, during the first visit to the Golmore Jungle, Coeurls will be significantly higher level than your party. So the likelihood of obtaining one then is pretty slim.
Zodiac Age Version
In the Zodiac Age version, you can obtain an Embroidered Tippet much earlier than the original version. On the way to King Raithwalls Tomb, in the Nam-Yensa Sandsea, a non-respawnable chest was added that contains this item.
Embroidered Tippets can still be obtained from Coeurls, but there is a slight change on how to get it. Rather than using the Steal technick, you must use the Poach technick. By doing this, there is a 5% chance you will get one.