Therefore, although we measure distance in light years, it doesn't lead to twice the duration if we traveled at half the speed of light. In fact, as we approached relativistic speeds, the duration within our frame of reference would stay the same, but from an external point of view, our speed has not actually reached such a velocity.
Um, what? If it's 500 ly away, and something goes there at c/2, it takes 1000 years. What else could a speed of "half of lightspeed" possibly mean? Even relativity isn't so weird as to change that.
Therefore, we would perceive the time to travel to a nearby star as shorter than the value arrived at by a simple ratio applied to c. Likewise, the actual time passed on the target planet will have been many times longer by the time we get there such that we cannot assume that millions of years haven't passed since we first set out from our own home planet.
You're right that the passengers on the trip would experience less proper time than the observers on Earth (I believe this is really due to the acceleration involved, although it can be calculated using SR). But the time as measured by clocks on Earth and the destination will still be the one millennium you would expect from Newtonian physics. (What would surprise Newton is the anomalously large energy required to get to that speed, and the bizarre view out the window had by the travellers.)