We characterize all signed Minkowski sums that define generalized permutahedra, extending results of Ardila-Benedetti-Doker (Discrete Comput. Geom. 43 (2010), no. 4, 841-854). We use this characterization to give a complete classification of all positive, translation-invariant, symmetric Minkowski linear functionals on generalized permutahedra. We show that they form a simplicial cone and explicitly describe their generators. We apply our results to prove that the linear coefficients of Ehrhart polynomials of generalized permutahedra, which include matroid polytopes, are non-negative, verifying conjectures of De Loera-Haws-Koppe (Discrete Comput. Geom. 42 (2009), no. 4, 670-702) and Castillo-Liu (Discrete Comput. Geom. 60 (2018), no. 4, 885-908) in this case. We also apply this technique to give an example of a solid-angle polynomial of a generalized permutahedron that has negative linear term and obtain inequalities for beta invariants of contractions of matroids.