I highly recommend Mindfulness-Based Stress Reduction (MBSR) classes. Meditation is part of the practices, but there is more to it than that: some things which can really help perfectionism, like non-judging awareness, non-striving... the focus is on learning to be comfortable with yourself.

Yoga is good too! It's body meditation.