Here's how I did it for my fae trickster that's sitting in my bag of character ideas:
Play as a fae servant bound to the party's wizard (sort of like Bob, only not stuck in a skull). Say the wizard's great-grandfather did a big favor for Titania a while back, and she granted a vassal for him and his descendants. Work out the specifics with the other player; give them a decent working relationship, the fae gets days off, allowances for danger, etc.
As for the whole "free will" thing, if it looks like a duck, smells like a duck, and quacks like a duck. Give him a contract clause allowing him to ignore the wizard's commands in certain cases, give him stuff he likes to do on his days off, give him some basic personality traits, and it'll be close enough.
Since this setup relies on there being a wizard in the party, fae magic would probably be redundant. Instead, I suggest maxing out Deceit (since Greater Glamours can be done with Deceit or Discipline), and assuming the role of "face" and/or illusion support. Add a stunt that boosts Deceit when you're not lying directly to represent the fae's whole lying-while-telling-the-truth thing.
In essence, this setup could leave you rolling +7 Deceit in a lot of social situations, plus rolling +7 on veils and glamours, while still leaving plenty of refresh and skill points for balancing your role.
"no-lying" thing: treat those as compels on your High Concept. This could also apply to things like thresholds.
Cold Iron: With a cold iron Catch, Supernatural Recovery would only cost -1 Refresh, and it's a really useful power.