Yo suelo usar mp4 avc con doble pasada a 720x480 (es la maxima resolucion que pilla la PSP creo) con un 1500 de bitrate para ver videos en la tele (con la slim). Acaba ocupando mas que el original, pero vale la pena. Es la máxima calidad que he podido usar. Lo hago todo con el VisualHub (macosx, en Windows ni idea) y la verdad, se ve muy bien con el cable por componentes (aunque muchas veces depende de la calidad del video original, claro).
Para cosillas que no me prima tanto la calidad le bajo el bitrate y ya está. Y para verlo en la PSP y no en la tele, le bajo la resolución a 480x272 creo que era, no la recuerdo de memoria y con un bitrate mas bajo. En la PSP no se nota tanto la bajada de calidad del video como cuando lo ves en la tele, para verlos en la tele los tienes que cuidar bastante para que se vea en una calidad aceptable.