There are plenty of set plans that will work for anyone starting out. Starting Strength, Strong Lifts, New Rules of Lifting etc.

Personally I tell people to steer clear of personal trainers. If only I could recount the amount of crazy (and sometimes dangerous) things I've seen them get their clients to do, all in the name of "getting fit". Stick to big compound movements like squat, bench and deadlift and that'll be more than enough past just the starting out stages.