Well, stealth in Crawl is kinda weird. I recommend going Spriggan or Vampire if you want stealth. Naga can do it too, but I don't think it's a good idea. Tengu are pretty bad at stealth, as it requires Hex and Charms - they are usually either summoners or air conjurers.But I like being a ninja birdie *squish*
If you don't aim at winning the game, you might want to start as assassin - guaranteed blowgun can carry you up to Lair.
Also, while stealth is godlike for 3-rune runs, it is almost useless for 15-runes.