A brushed motor mechanically alternates the magnetic field, a brushless one doesn't. In general, brushless is more efficient (hobby-wise), but the electronics cost more because you need a more advanced speed controller. So yes, for all hobby purposes, brushed and brushless are incompatible.
Of course, you probably only need brushless if you want to make your robot a) go really fast or b) fly.
A servo is a motor and a potentiometer and the associated electronics, so you have a feedback loop and can find its position. It also doesn't spin continuously, unless you modify it. Since it doesn't require an external H-bridge, which is needed for standard brushed DC motors, its popular among people looking for a simple-to-use motor with a built-in gearbox.
For the wheels, the red X is a servo horn, which comes with the servo. It is screwed onto the wheel with holes you usually have to drill yourself, and then the horn is screwed to the servo through the axle hole on the wheel. Usually, you won't be able to friction-fit wheels (a la Lego), because of the varying standards in wheel shaft sizes and shapes.