I usually take Small Guns, Sneak and Throwing.
Once I get the Tag! perk, I tag Energy Weapons.
Throwing is a good secondary fight skill throughout the game: lots of grenades! Plus: you can throw through walls! If your perception is good, you'll be able to sense thugs through walls. If you have the Throwing skill, that'll save you a lot of trouble in some missions!
Small Guns is necessary - imho - because you don't find any energy weapons until the second half of the game. It ruins the pleasure if you have to wait to successfully kill anything until then.
Sneak is a good skill throughout the game. You do get a penalty when wearing better armour, but if your character has got a good ST stat, it's quite feasible to carry around a set of leather armour, unequip your PA, put it in your inventory and use the leather armour to do all the sneaking. A good Sneak skill + a good shotgun with the right ammo makes for one powerfull character throughout the game. The shotgun requires a good Small Guns skill, of course.
What's wrong with Stitch as a medic? He's got a lousy perception, true, but I remember him actually being quite good from midgame to endgame.
Rebecca is the one to use for Lockpick. She's also one hell of good shooter.
Rage is awesome as well. Good Sneak skills.