Hooola, vamos a ver...
El encoder no hace que el motor sea mas rápido, solo que se pueda controlar mejor.
Yo usaría motores de corriente contínua normalitos. Usar encoders en esta aplicación no te aportará nada, a no ser que quieras un control de posición 2D (o sea, saber donde esta en robot en el suelo). Si solo quieres control de posición angular para que se balancee te basta con el giróscopo para hacer la realimentación.

PAP: control muy fácil, precisión en posición y velocidad. Lento y de poco par muy constante, mucho consumo, electrónica sencilla.
CC(sin encoder): control facil, sin control de posición ni velocidad. Rápido y de mucho par, pero no a bajas RPM. Poco consumo, electrónica muy sencilla.
CC(con encoder): control dificil, control de posición y velocidad. Rápido y de mucho par pero no a bajas RPM. Poco consumo, electrónica compleja.
BRUSHLESS: control complejo, muy alta precisión en posición y velocidad (si se usa encoder). Muy rápido y de mucho par incluso a velocidad cero. Poco consumo, electrónica muy compleja.

En tu caso las mejores opciones son CC y BRUSHLESS dependiendo de lo que quieras hacer con el robot y de lo que te quieras complicar la vida (y presupuesto).
Consideras necesario mas par motor sacrificando velocidad?
Para esto tienes que hacer un poco de matemáticas. Tienes que ver la cinemática de tu móvil y calcular que valores de velocidad y par necesitas para que el robot sea controlable. Si no, en cuanto se desvíe unos grados de la vertical, no tendrás par para levantarlo.
En cualquier caso los motores CC a baja velocidad no dan apenas par, necesitaras o sobredimensionarlos mucho o usar un pequeño reductor. Un motor de CC llega sin problemas a 10.000 rpm, un prqueño reductor no te restara velocidad util.

Por otro lado siempre tendrás que hacer un acoplamiento entre las ruedas y el motor, no suspendas el robot de los ejes del motor que sufrirá mucho. Las ruedas necesitan sus propios ejes y casquillos para aguantar el esfuerzo.
¿Es un proyecto académico, para enseñar y listo, o pretendes que dure rodando bastantes kilómetros? Para lo primero sirve cualquier cosa estilo "tente mientras cobro" pero si quieres que aguante mucho tiempo hay que afinar mas en la mecánica.

Dragonet ya te ha explicado muy bien los motores, así que no me extenderé sobre eso.

Para el tema del control con un giroscopio no te bastará, ya que tiene una deriva que te terminará por tumbar el robot. Mejor un duo giroscopio + accelerómetro.

Con el accelerómetro ajustas el P y con el giroscopio ajustas el D, como lo explico aquí: http://skiras.blogspot.com.es/2012/10/4copter-fusion-de-sensores-i.html " onclick="window.open(this.href);return false;

S2

Ranganok Schahzaman

Muchisimas gracias a ambos.

Es un proyecto personal, así que pretendo que aguante bastante. He de reconocer que la parte mecánica es la que peor llevo, pues estudio electrónica.
Voy a buscar mas información sobre los motores BRUSHLESS.

Me recomendáis alguna tienda para comprar por internet motores, reductoras, ruedas?

En cuanto a la parte de electrónica, es mejor comprar:
1.- giroscopio + accelerómetro, en la misma placa
2- UN giroscopio + UN accelerómetro, en placas diferentes?

Algo así?? http://dx.com/es/p/gy-85-6dof-9dof-imu-sensor-module-for-arduino-148436?tc=EUR&gclid=CK6Uz5OUkL0CFUsUwwodlGAA6Q#.UyH7Lvl5NLI " onclick="window.open(this.href);return false;
En cualquier caso, recomendáis alguno? Y donde comprarlo?

Gracias de nuevo

Muy buenas,

He estado mirando los motores paso a paso y he seleccionado estos:

http://www.pololu.com/product/1208 " onclick="window.open(this.href);return false; -> 12.95$ NEMA:14 PESO: 140g PAR:1kg-cm (creo que me puede valer)

http://www.pololu.com/product/1209 " onclick="window.open(this.href);return false; -> 15.95$ NEMA:14 PESO: 180g PAR: 1,4 kg-cm NO STOCK (es mejor?)

http://www.pololu.com/product/1204 " onclick="window.open(this.href);return false; -> 15.95$ NEMA:8 PESO: 60g PAR: 180g-cm (demasiado pequeño? poco par?)

http://www.pololu.com/product/2267 " onclick="window.open(this.href);return false; ->16.95$ NEMA:17 PESO: 285g PAR: 3.7 kg-cm (Este le veo excesivo, Creo?)

Que os parece? En la web pone que hasta principio de abril, supongo que podría esperar.

En cuanto al "afine" de mecánica no tengo ni idea de como hacerlo. He estado mirando el sub-foro de mecánica pero no encuentro mucho. Alguna ayuda?

Gracias de nuevo.

Lo que hay en Pololu y Sparkfun tambien puedes comprarlo en Bricogeek. Preguntale si tiene algo en stock.