We investigate numerically the three-dimensional three-state Potts models with nearest-neighbor (NN) ferromagnetic coupling and next-nearest-neighbor (NNN) antiferromagnetic coupling of relative strength-gamma on L3 lattices with L = 12, 16, 20, 32, and 40. For all the gamma-values that we studied, 0.0 less-than-or-equal-to gamma less-than-or-equal-to 0.8, we find indications of a first-order phase transition between the ordered and disordered phases. In the neighborhood of gamma = 0.25, the latent heat becomes rather small, making it necessary to use still larger lattices to rule out a higher-order phase transition at gamma = 0.25. We also studied the boundary regimes of the three different ordered phases and find no criticality along them, thus suggesting a lack of criticality in these extended Potts models.