Is it worth it? Most certainly. My friend went from making 220whp on a Cobb map to 252whp on a Pro-Tune. And no, I think you can do better than $500. Try $300-350 if you are cool with a tuner, and work them a little. There are a few cool ones here in CO.
If you plan on having any fun in your car whatsoever for the next few years you're here, get a Pro-Tune. You won't regret it. I haven't talked to anyone who ever has. You can worry about re-tuning it once you get back down to sea level. Coming from sea level, I imagine you will get frustrated sooner or later and save some $ for a Pro-Tune. Just stop eating fatty cakes.