Despite established roles in human health and profound global diversity, microbiome datasets remain biased toward Western urban cohorts, with especial under-representation of Southeast Asia. Here, we present a gut microbiome dataset from 116 Indonesians spanning transitional hunter-gatherer, rural agricultural, and urban lifestyles. We identify 1,304 species and 3,258 subspecies by assembling 11,070 metagenome-assembled genomes, revealing substantial species- (15%) and subspecies- (50%) level novelty. Novel taxa are rare, often village specific, and depleted for sporulation genes, revealing a link between bacterial physiology, transmission, prevalence, and discovery. We identify rural-to-urban clines across multiple levels of biological organization, from species abundance to microbiome composition and diversity. Furthermore, between-community, but not within-community, diet variation is strongly predictive of microbiome composition, suggesting that microbiome divergence is driven by community-level differences. Our work highlights the interplay of host lifestyle, population structure, and bacterial physiology in shaping microbiome diversity and biogeography, at the key scale of human communities.