Despite many potential advantages, Advanced Metering Infrastructures have introduced new ways to falsify meter readings and commit electricity theft. This study contributes a new model-agnostic, feature-engineering framework for theft detection in smart grids. The framework introduces a combination of Finite Mixture Model clustering for customer segmentation and a Genetic Programming algorithm for identifying new features suitable for prediction. Utilizing demand data from more than 4000 households, a Gradient Boosting Machine algorithm is applied within the framework, significantly outperforming the results of prior machine-learning, theft-detection methods. This study further examines some important practical aspects of deploying theft detection including: the detection delay; the required size of historical demand data; the accuracy in detecting thefts of various types and intensity; detecting irregular and unseen attacks; and the computational complexity of the detection algorithm.