Yo te recomiendo Hyperion. Sencillamente el mejor ciclo de scifi de la historia (siempre bajo mi punto de vista, claro). Además el formato del primer volumen es muy apropiado para primerizos. Pues son como relatos cortos unidos por un hilo conductor, al estilo de los cuentos de Canterbury. La saga completa (incluidos los "endymiones") es sublime. Aúna lo mejor de toda la historia de la scifi. Todos los géneros posibles contenidos en una sola saga.
Aunque también es verdad que puedes empezar por algo más ligerito y reservar los Cantos de Hyperion para cuando seas un lector scifero más experimentado, así la paladearás más, sin duda.