Do evaluation / recruiting committees respect "co first authors"?
In theoretical computer science and mathematics, authors are (almost) always listed alphabetically. There is simply no such thing as a "first author", except lexicographically.  Equivalently, all authors are co-first authors.

In my experience, recruiting committees generally understand and respect this practice, but (at least in computer science, where order by contribution is more common) they do occasionally have to be reminded, especially for candidates whose last names start late in the alphabet.  One sentence in the CV and/or in a recommendation letter usually suffices.

For non-theoretical CS, I have seen CVs that indicated equal contribution of co-authors. Again, one sentence in the CV ("Stars indicate co-authors who contributed equally") made the notation clear, and the recruiting committee understood and respected it.

As Ari and gefei say, having a local advocate is much more important that having another (co-)first-author paper.  If nobody on the faculty is willing to pound on the table and demand that you get an interview, you won't.