"Any exercise" gets my vote. It seems to me that a lot of people - myself included - get wrapped up in the body hack mentality (4-Hour Body?) or in finding the "best" exercises, when the important thing is just to get moving and make it fun.
Most exercise is going to hurt a bit if you've lived a relatively sedentary life. There is a difference between the pain of "my body isn't used to activity" and the pain of "ZOMG, my heart is going to explode." Pain is just weakness leaving your body.
Perhaps I should add "and listen to your body" to my previous comment.