I've been to Puerto Vallarta a few times and both times I ran on treadmills. There is a paved path (melicon that is maybe a mile to a mile and half long that follows the beachline, but it gets crowded by mid morning if the weather is nice. The side walks are very uneven depending on in if you're going up or down a hill. The streets are either asphalt covered cobbles or just cobbles. Cars, cabs busses and motor cycles are all over the place and care little for pedestrians

Given what has been going on in Mexico over the past few years with the drug cartels I wouldn't venture off the beaten path, but maybe I'm overly cautious.