If you enable the table column click sort on a taxonomy field, it will seem to sort randomly. This is because the sort is by Term ID, not Term Name. To make the tables click sortable by term name:
- Add a Relationship for each Taxonomy Field.
- Add a "Taxonomy Term: Name" field for each one and select the related Relationship.