My personal preference is for marching tetrahedra over marching cubes because it avoids an awkward ambiguous case and just seems generally much simpler with only 8 possibilities for the way the surface can pass through 1 cell instead of 256.
Using midpoints of edges gives a very chunky looking result, whereas linear interpolation should be good enough for most purposes and is pretty straightforward to do.
For anything other than the coarsest mesh, I think checking for intersections in every single sub-cube would be really slow, so I guess one should use an octree approach to narrow it down.
