Didn't do any serious comparison or research but I'd bet half of my money on perception as well.  Correct me if I'm wrong but I think it's high perception not agility that allows you to avoid traps, some encounters and getting back stabbed by brigand for instance. As for the perks helpful ones are probably Stealthy, Faster and Smarter, depending on how ur points are allocated Wellrounded and Specialist can be of use too by further boosting ur Per or Agi. 

Other than that just save before attempting and don't be greedy, even with high stats boosted by items like Shoes of Running won't let you rob the clerk to his/her bare ass without getting caught. Honestly though only reason I did steal anything was to actually get caught ;-)