Grendel's Children has a bunch of unusual, not always cute, tiny avatars that she might like. They're also really, really cheap and some are free. They're all very customisable which makes them easy to make your own. I liked the clockwork mouse, but you can wander around and you'll find quite a lot of less cutesy, untraditional tinies.
I also tend to hit extrovirtual (I think it is, Wynx's place and the shops nearby) and have a wander around there to look at the tinies. They're traditionally cute ones though, but they're fun especially since there's lots of clothes you can buy elsewhere that fit the avatars.
The first tiny I bought was a dragon too, from Isle of Wyrms, just so I could put on Siyu Suen's Zorro outfit. It was so much fun having a cloak, a stabby sword and a hat whilst being tiny. (The clothes are made for the hedgehogs but are easy modifiable to fit other tinies.)
Barerose has (or had) maybe two or three tinies, what I liked best was the tiny clothes they had though. They were fun.
The other one that I'm quite fond of is my siamese kitten, (I like tinies on four legs), which I bought a pounce attachment for so I can pounce on others, and cute little wings, and found a bunch of free cat sounds. I like the animations, how it'll lie down and stretch, the claws extend and retract, it'll sit and wash its face and that sort of thing. A couple of my friends bought them too and we'd run around chasing eachother and we each added some attachments (my friend put a crown and a necklace on hers) for fun and to make them a bit different. I'm not in world just now so not quite sure where it was I got it from. If it's at all interesting to you or your friend drop me a reminder and I'll check.
When I'm searching for something to buy, in such a broad category as "tiny" what I usually do is I get slexchange.com and onrez.com and browse online. I'll stick the terms I want in the search engine and wade through pages of stuff which I find easier than doing all my shopping on secondlife. Then I'll jump in world and go to the shop and have a look at what's in the store and maybe surrounding shops if it's a mall.
I did hit slexchange and it seems that there are a few tiny fairy avatars out there. Most of them are anime-styled, and you could also buy a tiny anime-girl and slap some wings on her to make her a fairy. I'm sure you're as capable of using search engines as I am so I won't stick down a bunch of links here.
I did see a pretty small fairy avatar in world before only not being interested in having a tiny female avatar I never took note of where it was from, so I know there's a few out there.
Hmm I think
http://slexchange.com/modules.php?name=Marketplace&MerchantID=65397 is also pretty short (from what I remember seeing in world). Not tiny-tiny but not as big as a normal avatar. Or I might be thinking of somethinge else.
Good luck on your search though and I hope you have a lot of fun.