Possible option. By default pick either sort by date or sort by message index, and let the user set the other option in a config setting. Squirrelmail for instance has an option in setting 'Sort by received date'. As an admin, I can then choose to hardcode that option for every user and not allow them to change it.
It seems to be the most intuitive for the users. +1