We show that near-spherical micrometer-sized colloidal particles at an interface of two fluids experience inter-particle forces merely as a consequence of their shape-induced capillary interaction. The interaction is strong even if the deviations from sphericity are on the nm-scale, and can hardly be avoided in experiment. For particles of 2 μm radius, a deformation of 20 nm can result in an attractive potential of 2kBT at a distance of 4 particle radii. Dynamical simulations of many particles confirm that the forces lead to aggregates of dendritic or hexagonal-lattice type. The latter pattern exhibits strong herringbone-phase orientational order.