I think the key is to define what constitutes "activity". 

What would the activity of paleo people be like? I can see lots of walking, carrying heavy loads, sprinting (although there probably was a certain amount of longer distance running), dancing, playing various games, probably (at least among men) strength competitions ("I can lift this log/rock/etc. more times than you can"). For spear-hunting/bow-shoting paleos, lots and lots of practice. Including practice at throwing rocks. Women, who likely did much of the long-distance carrying, probably had their own competitions - perhaps that's where "balancing" and the more graceful sports originated.

I think Ken O. posted excellent advice - try to get back to your teenage activity level. As a teenager I was not really into lifting weights, but I did do a lot (and I mean *a lot*) of cycling and hiking (and fishing). I've succesfully reintroduced the cycling part, now I need to work a bit more on the hiking/fishing part.