I just turned someone down today who was by all accounts competent, but just came across as the kind of person I wouldn't want to work with.

You might want to take a lot more time working on that personality if yours. Everything you wrote in your post and your post's general tone screamed to me "humorless with a chip on his shoulder."

And dump the self deprecation bit. No one's gonna hold your hand here. I doubt you're a bad programmer, I just think you suck at being likable. Shitty, I know. Now do something about it. Much more than you've been doing. Be approachable. Politics will always get your much further than skill.