Playing a stealth thief, I find that followers (specifically Lydia) are not useful on missions.
She just keep getting us detected, so I'm forced to tell her to wait before starting a mission, which is annoying given that almost all dungeons have alternative exists that make me have to go back and get her again.
Is there a follower that would go well with a stealth character or should I not use any follower at all?
Any follower that is skilled at light armor and sneak (and optionally, archery too) should be fine. Followers should preferably be non-mage, as casting spells will attract enemies and blow your cover. Complete list of followers and their descriptions here: http://uesp.net/wiki/Skyrim:Followers
Followers that are good at sneak, light armor and archery are: Aela the Huntress, Cicero and Dark Brotherhood Initiate.
Tips to make followers extra-sneaky:
Also, note that (from the UESP wiki's "Skyim Followers - Follower Stats" article):
A follower levels up according to the PC's level up to the follower's maximum level (which varies for each). With few exceptions, each follower has a maximum level, and a specific set of primary skills, which are dictated by their class.
Prior to patch 1.6, a follower's skills, health, and other stats were set when they were first spawned (which is typically when you enter their starting cell, become a Thane, and so on) and would not increase as their level increased. Prior to the fixing of this failure of stats to update with patch 1.6, players could update a non-essential follower's stats so they would increase based on their current level by using the Wabbajack to polymorph them into another creature, after which their stats would update upon recovering their original form. Players of the PC version could also use certain console commands to fix any follower's inability to update their stats with each level.
So in most cases, leveling up the player character will also make your follower level up, increasing the follower's sneak skill (the maximum and by how much, will depend on the specific follower and their NPC class).
I prefer mage followers if I'm trying to be stealthy, since they do not wear obnoxiously loud armor and are relatively obedient.
One notable mage follower is J'zargo in the College of Winterhold. Whether it is a bug or intentional, he matches your level unlike other followers. This gives him some beefy HP when you get to higher levels. You can recruit him by doing his undead scroll test quest.
If you want a very powerful but not quite as stealthy follower, try Aela the Huntress after you get through the Companions quest line.
For more thiefy-type followers, a few become available during the Dark Brotherhood quest line. If you don't kill Cicero, he becomes available later. At the end of the quest line, you can just draft an initiate.
Now, all that being said, sometimes people's playstyles just clash with the follower AI. If a mage or thief-type still causes you grief, it may just be time to hang it up and go solo. Followers aren't truly necessary for anything other than the scripted quests that give one to you.
For my stealth-oriented thief/archer/assassin character, I find Lydia to be an invaluable asset in easily 80-90% of circumstances. It does take care, though -- she's noisy, especially in the upgraded armor I've given her and carrying that big, heavy, two-handed axe I gave her, so for spots where I want to sneak on ahead and quietly take things out, I tell her to wait, then come back and get her when it's time to move forward again. And, yes, I sometimes do have to tell her to just wait for me while I solo a particularly tricky area that requires absolute stealth -- like most Thieves' Guild quests, for example.
What makes her truly invaluable though is having the closest equivalent of a Sherman tank to back me up when stuff invariably hits the fan. She's proven a capable dragonslayer (although her giant-slaying skills mostly amount to method acting a hacky-sack...), and even when I've told her to wait somewhere she'll come sprinting forward to cover my back if I screw up and find myself having bitten off more than I can chew!
All this said, try out different companions until you find one that you like and that works for you, or decide you're better off just going solo. So far I've used only Lydia, but Aela and Jenassa seem like they'd be good fits for a stealth-oriented character, the former however requiring you to complete a somewhat lengthy quest chain, whereas the latter just wants 500 gold; I'll probably give each of them a trial and see then if I still like Lydia.
Faendal is also good.
He hasn't been too bad at being stealthy with my character as long as he has the right armour.
If you look at the wiki, it says that Cicero, Aela, Faendal, Brelyna and Ogol are sneak. I only listed them because theres something for everybody there. If you want heavy armored high sneak you got ogol, Aela and Faendal are archers, Cicero is a rogue/assassin guy, and Brelyna is a mage.
I was trying to find out the same thing whether there is any decent sneak companions. Turns out there really isn't any from the forums I've been searching, they all seem to run off into battles you don't want them to. However since sneak/theives aren't the best dragon slayers, a weapon I have found very useful is the Sanguine Rose. Without giving too much away this weapon allows you to summon a very useful character that will distract the dragon long enough to fill it with arrows. I can pump iron arrows into it and very slowly kill it without it even looking at me, very handy.
there is a mod on the nexusmods website, called Vilja companion: http://skyrim.nexusmods.com/mods/26393. It adds another npc that you can make as your follower. she has a questline and there are a lot of options for her. For example, you can give her a set of clothing and a set of armor. she changes between them depending on if she is in battle or she is using magic/not in combat. You can also tell her to use a specific style of combat. For example, you can tell her to stay back and use a bow, or stay away from battle altogether. There are a lot of options. i think she is also very stealthy, especially when you tell her to stay away from battle and use bow.
