A felony on your record might not hurt you that much, everything is a felony anymore.
A theft conviction definately will. People do sometimes change but you are going to have to prove yourself.
I agree with Dennis, construction is going to be your only hope. I don't think you will find anyone doing service work that is willing to risk his company's reputation on you when there are plenty of guys looking for work that have clean records.
Think of it like this, I hire a company to do work for me. One of the guys steals from me. Even if his insurance pays me for what he stole, I will never use that company again and I will be sure to tell everyone I know what a scumbag company it is.
I can't imagine anyone in thier right mind willing to risk that.