So I'm thinking of optimizing my textures to get a little bit more performance out of my game. Is it relatively safe? What program should I use?

DDSopt, and yes, it's quite safe. STEP has a decent guide for beginners http://wiki.step-project.com/Guide:DDSopt#tab=Using_DDSopt.

The only way I can get MSAA up to 4x is with optimized textures