Pues me parece que te vas a tener que gastar un poquillo mas de pasta, ya que un reproductor un poco bueno de 128 te viene saliendo por 130 euros (me refiero a un Iriver, Creative,...). Tambien tienes marcas como Energy System (ES) que no se que tal van, pero me parece que de precio por el estilo.
Por lo de la capacidad 128 Mb bien comprimidos (96 Kbps) son suficientes (Aprox. 2 discos), esta claro que 256 es mejor, pero tambien es mas caro. Yo tengo un Iriver IFp-180T de 128 Mb y estoy muy contento (vale no se le puede meter OGG, pero y que) normalmente le suelo meter entre 20 y 27 canciones entre 128 y 192 Kbps, aunque he conseguido meter algo mas 50 comprimiendo en WMA y a 58 Kbps (al principio suena raro, pero despues el oido se habitua, aunque se nota la diferencia).