I'm attacking with 2 dice -let's say I roll 1 regular hit and a critical hit. If my opponent chooses to exhaust an Evade Defense Token to remove one of my attack die from the pool can he choose the critical hit die, or does he have to remove the regular hit die first?

You can remove any die. Critical hit effects are resolved after defense tokens are used. Check out the Rules Reference for Attacking and Critical hits, this will give you a run-down of the attack sequence.

Thanks!