A common question around here, with a semi-known but largely-unknown answer.
The earliest time you can get is when you have access to Fluorgis (just after the aerodome quest). Thereafter, you may be blessed with a Gria wanting to join a clan, in Fluorgis, in the month of Emberleaf (the last month of 20 days prior to an Auction season). She will appear as a "?" on the area map.
I :heart: tomatos? http://img168.imageshack.us/img168/2882/cc29ce7.jpg
In case anyone was wondering, I got the recruitment quest during Emberleaf (the month both Grias and Seeqs should show up), and the recruitment guy, who usually says what species you can get, said he had "all types" that month. I tried every combination of answers, and only ended up with only Seeqs and a whole lot of "you need to do a quest for this job" responses. This is odd, as I already managed to unlock a Gria class, so roughly half of the Seeq/Gria jobs should have been open.
In other words, yeah, I'm pretty sure there's a point you have to go past for them to be available, like the OP says.