We find solutions of a gravity-Yang-Mills-Higgs theory in four dimensions that represent asymptotic anti-de Sitter charged black holes with partial/full gauge symme-try breaking. We then apply the AdS/CFT correspondence to study the strong coupling regime of a 2 + 1 quantum field theory at temperature T and finite chemical potential, which undergoes transitions to phases exhibiting the condensation of a composite charged vector operator below a critical temperature Tc, presumably describing p + ip/p-wave su-perconductors. In the case of p + ip-wave superconductors the transitions are always of second order. But for p-wave superconductors we determine the existence of a critical value αTc of the gravitational coupling (for fixed Higgs v.e.v. parameter mW) beyond which the transitions become of first order. As a by-product, we show that the p-wave phase is energetically favored over the p + ip one, for any values of the parameters. We also find the ground state solutions corresponding to zero temperature. Such states are described by domain wall geometries that interpolate between AdST4 spaces with different light velocities, and for a given mW, they exist below a critical value of the coupling. The behavior of the order parameter as function of the gravitational coupling near the critical coupling suggests the presence of second order quantum phase transitions. We finally study the dependence of the solution on the Higgs coupling, and find the existence of a critical value beyond which no condensed solution is present.