How can I get blog categories and blog entry urls to play nice together?
I think the problem here could be to do with the path to your Category Template.

Make sure that in your category settings, the path to your Category Template file includes the folder it is nested within.

So instead of _category.html, you should put blog/_category.html (if that file is inside the Blog template folder)

There is also some docs on the Craft site that tells you how to template this file if you haven't seen it already.