JB's on Fort Road is good (talk to Gary or Zane), Mopac, Certified Radio on Whyte (talk to Ralph), Jarman Mazda (for OEM stuff; if you're a member of the local club you get decent discounts on parts/labour), for a good Mazda mechanic - that's not a dealer - go to Abbey Road Auto and talk to Jim (he's one of our founding members and is a Mazda Master mechanic, real good guy to deal with), Apex is pretty good too. Protege Garage, though not local obviously, is also excellent to do business with; Ken's awesome, as just about everyone on here will agree.
Hope this helps!