Hola:
Cuando es un rpm creo que se puede pasar a deb con un programa que se llama alien, nunca lo he usado pero seria algo asi como :
>alien nombredepaquete.rpm
>dpkg -i nombredepaquete
Mas informacion aqui
http://bulma.net/body.phtml?nIdNoticia=1186
Los deb son los paquetes para sistemas debian, ubuntu o knoppix y los rpm son los de sistemas basados en redhat o mandriva.
Para el tar.gz lo mas normal es que lo descomprimas y lo compiles, para descomprimir no me acuerdo del comando concreto aunque seguramente lo puedas hacer graficamente.
> tar xvfz archivo.tar.gz (si falla es porque no es xvfz sino xvf y otra letra que no recuerdo)
>cd directorio_que_ha_creado
>./configure (esto mirara si tienes todas las librerias que hacen falta, si falta dara un mensaje de error, instalala por synaptic)
>make (para compilar el programa)
Para el ultimo paso hay que ser root, pero solo es si quieres instalar el programa para todos los usuarios, sino seguramente desde el home puedas ejecutarlo sin problemas
>make install
Bueno, esto de los tar.gz es para los programas a compilar, que es bastante normal, si que hay mas casos pero a mi no me ha hecho falta nada mas.
Saludos