Hombre, pues es muy relativo. A cada cual le serán imprescindibles unos tipos de programa según sus aficiones o a lo que se dedique.
Personalmente, encuentro imprescindible el OpenOffice.org, Mozilla/Firebird y GIMP, a partir de ahí pues cosas como Kile (para hacer trabajos de calidad), K3B (para grabación de CDs), xmms (como reproductor multimedia), mplayer (como reproductor de video), Xmame, Tuxracer y Frozen Bubble (pa viciarme
), luego el resto ya es opcional, clientes de correo como KMail o Evolution, de jabber como Tkjabber, Psi o Gaim, para programar Gvim o KWrite + GCC, La tetera
para que te avise cuando te preparas un té...