Strength training 3x a week. Why strength? Strength is the most generalized adaptation there is. Training to be strong improves every component of fitness: strength (duh), power, agility, balance, flexibility, endurance (all 3 types) and coordination. I would also make the argument that in day to day life strength is the most important attribute of fitness for someone in the western world. The ability to carry a bunch of heavy bags of groceries, to rack a computer, help a loved one in an emergency etc., almost all depend primarily on strength. It's also the primary adaptation for injury prevention and rehab (knee and back especially).
People may have different fitness goals, but for someone who is untrained by far the best thing they can do is a strength program for 3-5 months before training more specifically for their goals. I'd recommend Starting Strength, which is a simple and popular program (popular is important, because like certain programming languages it has tons of community support behind it so it's easy to ask questions and get answers). http://www.startingstrength.com/
People may have different fitness goals, but for someone who is untrained by far the best thing they can do is a strength program for 3-5 months before training more specifically for their goals. I'd recommend Starting Strength, which is a simple and popular program (popular is important, because like certain programming languages it has tons of community support behind it so it's easy to ask questions and get answers). http://www.startingstrength.com/