What I would do:
1 - Impressed with your work, potential paper with him
2 - Published a paper with him
4 - Impressed with your work
3 - Does not know you well. So, even if she is very well known, I guess she can't write much about you.
5 - Not a PhD, not a professor.
5 might still be an alternative, if applying to UChicago, for example. If possible, I would then send 4 letters.