If you want to go all the way down to transistor level to get a simpler circuit, there are more ways to simplify the circuit. For instance, using NMOS instead of CMOS lets you use a resistor instead of 2 PMOS transistors for a NAND gate, which might be worthwhile if you don't need a strong 1 and you're using discrete components.
Also, floating gate MOSFETs with multiple gate signals can be used to implement logic gates, and even multiple value logic, with very few devices.
You probably don't care about transistor level right now, but it's something you want to consider as some point. NOT, NAND, and NOR are the easiest (fewest transistors) to make in CMOS, so other gates are usually composed of these.
Side note: simplest isn't necessarily the best - you might want to even out path times to avoid glitching.