Some of the most popular motors and gearboxes are from the AndyMark NeveRest series. They come with built-in encoders (cable sold separately), and they do not burn out as easily as other motors. These motors are available with 3.7:1, 20:1, 40:1, and 60:1 reduction gearboxes already attached; however, you can buy the motor on its own and attach any number of other gearboxes.
For example, there are several Banebots P60 gearboxes compatible with the NeveRest motors (also available from AndyMark). These gearboxes offer a wider range of gear reductions, so you might seek them for a particular use. Using them on a NeveRest motor does require some assembly, however the folks at AndyMark have created a nice video to help:
Overall, the NeveRest motors and associated gearboxes are a great choice for many applications. When it comes time to program your new motors, check out the DC Motor guide.