Right now I'm choosing from Azata Lyrakien, Imp Consolar and Fearie Dragon.
Azata Lyrakien:
is quick (Init +8, perfect fly 80 ft and freedom of movement), perceptive (darkvision, low-light vision, constant detect evil and detect magic, Wisdom 17+3 and has truespeech). She doesn't have at will Invisibility, but I plan to give her ring of invisibility, so she will be really stealthy (18 stealth + 3 class +8 tiny + 20 invisibility = 49 – that should be enough till CR 17).
Imp Consolar:
is slower than Azata, perception is really good (darkvision 60 ft, detect good, detect magic, see in darkness, Wisdom 12+1). He can make himself invisible at will, but doesn't have stealth – which means that I should train myself. But he can change to whatever small or Tiny animal at will – which can be better than stealth.
Fearie Dragon:
is quicker than Imp, not so perceptive as Imp or Azata, stealthy as Azata (17 stealth + 3 class + 8 Tiny = 28, but also can use 3/day Greater Invisibility). His selling point is his 3rd-level sorcerer class, because that mean lot of cantrips (thanks to Cracked Orange Prism Ioun Stone.