I'm kinds stumped right now. I've been through a few different guesses at something that will work, but sofar nothing really has. I'm looking for any resources on how to pathfind in 3d space. Collision avoidance (triangle mesh, not just simple shapes) could work too, but I'd like something that, like A* on a grid, could always return a path.

Divide your world into cells. Some cells are connected to other cells by shared faces. This gives you a graph. A* is a graph search algorithm.