Etymologically, both pagan and heathen mean "rural"; "pagan" is "of the country(side)", cognate with Italian "paisano" and less erudite English "peasant". Heathen, on the other hand, is from an Indo-European root meaning "forest, untilled land". Looks to me like this means "heathens" are less civilized than "pagans", though along a shared line leading away from us* urban believers.

Haruo
*"us" here refers to the folks who coined the terms, not you and/or me