I say start with 2 full body workouts per week, INCLUDING LEGS. You say your legs don't need work...I say the quads are the largest muscle in the body, and by working them you burn more calories than workign any other muscle.
I also say squats are one of the most important exercises around, and barring a physical disability, should be performed often.
After a month you could do 3 full body workouts a week. In addition, do 3 days of cardio a week, 30-40 mins, and a variety (bikes, running, stairstep, elliptical, or aerobics classes)