It's probably best to slap on all the bolt on before you go get a tune or it's most likely pointless.
You'll fine some gains with the tune a stock vehicle, but it would be best to do as Mongolian said and get some bolt-ons first.
No problems with AWD, there are plenty of AWD FX's and G's that have safely been tuned. As far as tuners in your area, I'd go to UpRev's site and look for pro-tuners in your area.
I have done some of the "bolt-ons" already. I've done a Stillen exhaust and the Injen CAI. I am new to this "modding" thing, so I don't know too many other things. Have any other suggestions as to what I could add ?