Phals really aren't that picky about pot size in my experience. Go at least a half size up with them. I don't do Cyms, or Max. so can't help you there.
I would definately encourage you to do your best to pick out the old medium. If you leave it it will rot in the s/h, and you will end up with a mold problem. I would soak the root ball for 20-30 minutes in tepid water to limber the roots up so they won't break quite so easily. It will also soften up the leftover media and make it a little easier to get out. You're going to lose some roots, no two ways about it. I've found though that that often stimulates the plant to sent out new growth pretty quickly.
Those are my principles and if you don't like them......I have others.