Publishing a paper that's already been cited I do theoretical CS. A few years ago, I did some research and wrote a paper on my results, posting it on arXiv. I thought about getting it published, but between applying to programs after graduation and starting my new job, it fell by the wayside. Recently, I found a new paper is coming out that cites mine, disproves a conjecture, and extends a result.

Does the existence of the new paper hurt or help my chances of eventually getting the paper published? More likely, I would aim to present it at a conference because I've been told that that's much easier in theoretical computer science, especially for unknown authors or niche topics. Does the new paper hurt or help me chances of presenting the paper at a conference? It would feel weird presenting research that's no longer the state-of-the-art. Should the paper be modified to acknowledge the existence of the citing paper?
I think it should do more good than harm. The fact that you have been cited and your results extended means that your paper was relevant, which is a good thing. You definitely need to modify the paper though, not only to acknowledge the citing paper, but because you shouldn't publish a conjecture that is now known to be false.

Disclaimer: although I think the citation should help, this may be quite dependent on the particular reviewer(s) you get. The popularization of arXiv has been relatively recent in the CS field, and at least in many subcommunities the issues that come with it are still subject to debate and the "codes of conduct" are a bit blurry.