We study a recently discovered family of 1/8-BPS supersymmetric Wilson loopsin N=4 super Yang-Mills theory and their string theory duals. The operators aredefined for arbitrary contours on a two-sphere in space-time, and they wereconjectured to be captured perturbatively by 2d bosonic Yang-Mills theory. Inthe AdS dual, they are described by pseudo-holomorphic string surfaces livingon a certain submanifold of AdS_5 x S^5. We show that the regularized area ofthese string surfaces is invariant under area preserving diffeomorphisms of theboundary loop, in agreement with the conjecture. Further, we find a connectionbetween the pseudo-holomorphicity equations and an auxiliary sigma-model onS^3, which may help to construct new 1/8-BPS string solutions. We also showthat the conjectured relation to 2d Yang-Mills implies that a connectedcorrelator of two Wilson loops is computed by a Hermitian Gaussian two-matrixmodel. On the AdS dual side, we argue that the connected correlator isdescribed by two disconnected disks interacting through the exchange ofsupergravity modes, and we show that this agrees with the strong couplingplanar limit of the two-matrix model.