Check out
http://www.calgaryclimbing.com/ and
http://www.strongholdclimbing.com/
Both are local to me, fairly accessible and pretty decently priced.
I think Shannon and I are thinking about taking an intro to outdoor climbing in the spring. I'll let you all know how it goes!