First you need to decide if your going to work with color negs or black and white, or both. If you entertain even the most remote notion of ever doing color, you'll need a color head for your machine. Those are good because they can also be used for black and white variable contrast paper. If you're only going to do black and white, however, a variable contrast B&W head will be fine. It's also possible to buy an enlarger head that utilizes white light and you can place filters above or below the lens if you choose to use variable contrast paper (which is the most popular kind at the moment.)
The size of the baseboard is also important because it needs to accomodate the largest easel you'll be using for enlargements. Many baseboards only allow enlargements up to 11x14. If you want to enlarge further, you can wall mount the enlarger and not bother with the baseboard at all, or you can find some enlargers that will allow you to turn the head for projection on to a lower surface (the floor for example).
There are lots of enlargers available now as people give up their darkrooms in favor of digi prints on their printers, so don't hesitate to look into the used market.
Enlargers by Omega, Beseler, Durst, Saunders LPL, and Meopta come to mind quickly as reliable machines to consider but there are certainly others as well. Good luck.