How to decide on the order of authorship for this collaboration?
Here is a thought.  (Perhaps it is naive.  I haven't seen your paper, and I know nothing about the publication culture in computational linguistics.)  

Could you perhaps write two papers, with you appearing as first author as one and your collaborator on the other?  This would settle the issue symmetrically.  Whether it is a good idea depends more on how "bi-disciplinary" your work is.  By which I mean: is your work coming from two different camps, linguistics and machine learning?  If not, splitting is a bad idea.  If so, if you write one paper "splitting it down the middle" is there a ready-made audience who will appreciate the synthesis of both camps into a single paper?  If so, splitting is a bad idea.  But if not, you might find that your work reaches more people if you appeal separately to the linguistics and machine learning communities.

Again, just a thought.