The following criteria are what's most important to me:
1) Character balance -- some fighters will, invariably, be stronger than others, but none should dominate
2) Interesting fighting mechanics -- is victory achieved by ring out? TKO? Points? Whatever it is, make it engaging
3) Accessibility and depth -- it should conform to the video game maxim "easy to learn, impossible to master"